QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#578854 | #9264. Minimax Limit | ucup-team004# | AC ✓ | 469ms | 6740kb | C++20 | 3.1kb | 2024-09-20 21:56:08 | 2024-09-20 21:56:08 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
using F = long double;
constexpr F inf = INFINITY;
constexpr F eps = 1E-12;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << std::fixed << std::setprecision(10);
int n, A;
std::cin >> n >> A;
std::vector<int> a(n + 1);
for (int i = 0; i <= n; i++) {
std::cin >> a[i];
}
std::vector<F> len;
std::vector<int> type;
std::vector<int> l, r;
auto check = [&](F x) {
len.clear();
type.clear();
F lst = 0;
for (int i = 0; i < n; i++) {
if ((a[i] < x) != (a[i + 1] < x)) {
F r = i + (x - a[i]) / (a[i + 1] - a[i]);
len.push_back(r - lst);
type.push_back(a[i] < x ? -1 : 1);
lst = r;
}
}
len.push_back(n - lst);
type.push_back(a[n] >= x ? 1 : -1);
const int m = len.size();
l.assign(m, -1);
r.assign(m, -1);
for (int i = 1; i < m; i++) {
r[i - 1] = i;
l[i] = i - 1;
}
std::priority_queue<std::pair<F, int>, std::vector<std::pair<F, int>>, std::greater<>> pq;
auto getT = [&](int i) {
if (l[i] == -1 && r[i] == -1) {
return inf;
} else if (l[i] == -1 || r[i] == -1) {
return len[i] * 2;
} else {
return len[i];
}
};
for (int i = 0; i < m; i++) {
pq.emplace(getT(i), i);
}
while (!pq.empty()) {
auto [t, i] = pq.top();
pq.pop();
if (t > A) {
continue;
}
if (l[i] == -2) {
continue;
}
if (getT(i) > t + eps) {
continue;
}
if (l[i] != -1) {
int x = l[i];
len[i] += len[x];
l[i] = l[x];
if (l[i] != -1) {
r[l[i]] = i;
}
l[x] = r[x] = -2;
}
if (r[i] != -1) {
int x = r[i];
len[i] += len[x];
r[i] = r[x];
if (r[i] != -1) {
l[r[i]] = i;
}
l[x] = r[x] = -2;
}
type[i] *= -1;
pq.emplace(getT(i), i);
}
for (int i = 0; i < m; i++) {
if (l[i] != -2 && r[i] != -2 && type[i] == 1) {
return true;
}
}
return false;
};
F lo = *std::min_element(a.begin(), a.end()), hi = *std::max_element(a.begin(), a.end());
for (int t = 0; t < 50; t++) {
F x = (lo + hi) / 2;
if (check(x)) {
lo = x;
} else {
hi = x;
}
}
std::cout << lo << "\n";
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3844kb
input:
1 1 0 1
output:
0.5000000000
result:
ok found '0.50000', expected '0.50000', error '0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3980kb
input:
2 1 0 2 1
output:
1.4285714286
result:
ok found '1.42857', expected '1.42857', error '0.00000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4036kb
input:
1 1 -10 -10
output:
-10.0000000000
result:
ok found '-10.00000', expected '-10.00000', error '-0.00000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
1 1 -16 -25
output:
-20.5000000000
result:
ok found '-20.50000', expected '-20.50000', error '-0.00000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
3 1 -78 -36 -100 -100
output:
-58.9743589744
result:
ok found '-58.97436', expected '-58.97436', error '0.00000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
10 8 527518 -76819 -1000000 -1000000 -371619 -1000000 -1000000 -1000000 802779 -787512 -191827
output:
-829275.3457814248
result:
ok found '-829275.34578', expected '-829275.34561', error '0.00000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3972kb
input:
66 24 3314 3314 3310 3308 3306 3306 3310 3305 3309 3312 3309 3306 3304 3304 3298 3296 3292 3294 3290 3295 3293 3297 3294 3296 3290 3287 3291 3296 3301 3300 3306 3306 3305 3299 3304 3298 3299 3293 3292 3293 3290 3287 3285 3281 3283 3279 3278 3275 3271 3271 3276 3273 3268 3263 3266 3272 3270 3273 3273...
output:
3304.0000000000
result:
ok found '3304.00000', expected '3304.00000', error '0.00000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 4036kb
input:
222 2 -37639 -37066 -34986 -36518 -37278 -36636 -37610 -36500 -37912 -37814 -37433 -35611 -36632 -36923 -36869 -35293 -37162 -36769 -36400 -35797 -37157 -35545 -33431 -32046 -32089 -31558 -30628 -30485 -30620 -31334 -29666 -29133 -28572 -27031 -28287 -29533 -30351 -28294 -27028 -28080 -29576 -28885 ...
output:
-27438.7817672001
result:
ok found '-27438.78177', expected '-27438.78177', error '0.00000'
Test #9:
score: 0
Accepted
time: 3ms
memory: 4120kb
input:
1111 853 436575 1000000 -429113 -1000000 -1000000 936907 1000000 718335 687730 1000000 1000000 1000000 1000000 190580 1000000 -102181 1000000 1000000 1000000 -617146 -164387 -954651 148464 -132861 -1000000 -290001 -1000000 444489 -1000000 7783 -944405 -1000000 -577680 -1000000 -609355 -827090 -10000...
output:
106255.6261321070
result:
ok found '106255.62613', expected '106255.62581', error '0.00000'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3868kb
input:
6666 666 -270520 -312321 -315197 -290708 -233462 -298760 -346122 -353453 -355059 -393054 -356363 -343292 -356235 -382211 -341676 -330187 -384793 -440327 -482746 -533709 -569179 -610467 -588335 -560403 -587227 -551432 -530130 -561363 -603855 -614571 -578579 -628207 -640639 -656283 -601795 -664590 -66...
output:
277459.9073097084
result:
ok found '277459.90731', expected '277459.90732', error '0.00000'
Test #11:
score: 0
Accepted
time: 141ms
memory: 4380kb
input:
33333 1899 272208 -698774 -1000000 -426888 -357064 392257 379403 169592 -3709 -400809 86895 711138 -944795 -1000000 -1000000 440565 1000000 -346246 -1000000 -231003 -380171 1000000 324586 1000000 -120964 423685 -578248 350567 -543850 -1000000 32559 1000000 1000000 1000000 1000000 1000000 1000000 441...
output:
217445.7529714022
result:
ok found '217445.75297', expected '217445.75336', error '0.00000'
Test #12:
score: 0
Accepted
time: 458ms
memory: 6740kb
input:
100000 41764 593289 -840270 -659408 -246049 -1000000 -754807 -1000000 -1000000 -1000000 -1000000 -1000000 -1000000 -1000000 813897 -1000000 -1000000 -1000000 -11150 -1000000 613549 -722657 -1000000 533701 327368 1000000 -942410 -1000000 -1000000 861396 790723 304209 604892 -187240 -503129 -1000000 -...
output:
9246.7842913759
result:
ok found '9246.78429', expected '9246.78415', error '0.00000'
Test #13:
score: 0
Accepted
time: 469ms
memory: 6568kb
input:
100000 51453 -523799 1000000 1000000 111792 -729653 -219970 1000000 -965539 -1000000 374791 -884189 -1000000 596427 -317643 1000000 1000000 1000000 10146 -1000000 845949 1000000 663675 1000000 1000000 1000000 -4621 -701998 -290292 -606776 225408 -235717 -346140 -90603 1000000 1000000 1000000 1000000...
output:
19750.4660428542
result:
ok found '19750.46604', expected '19750.46583', error '0.00000'
Test #14:
score: 0
Accepted
time: 14ms
memory: 3820kb
input:
100000 53714 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977 -322977...
output:
-322977.0000000000
result:
ok found '-322977.00000', expected '-322977.00000', error '0.00000'
Test #15:
score: 0
Accepted
time: 14ms
memory: 3764kb
input:
100000 1 801681 801680 801680 801681 801682 801681 801682 801683 801684 801684 801683 801683 801684 801684 801685 801686 801685 801686 801687 801686 801686 801685 801684 801685 801685 801685 801686 801685 801685 801684 801683 801682 801683 801682 801681 801681 801682 801681 801681 801681 801680 8016...
output:
801987.5000000000
result:
ok found '801987.50000', expected '801987.50000', error '0.00000'
Test #16:
score: 0
Accepted
time: 14ms
memory: 4084kb
input:
100000 2 -432605 -432603 -432602 -432607 -432609 -432606 -432602 -432606 -432608 -432613 -432615 -432616 -432619 -432615 -432611 -432613 -432615 -432610 -432615 -432613 -432610 -432610 -432615 -432617 -432618 -432623 -432621 -432626 -432630 -432629 -432627 -432622 -432625 -432621 -432617 -432613 -43...
output:
-431914.3750000000
result:
ok found '-431914.37500', expected '-431914.37500', error '0.00000'
Test #17:
score: 0
Accepted
time: 14ms
memory: 3836kb
input:
100000 3 -872941 -872942 -872941 -872942 -872941 -872940 -872940 -872940 -872939 -872940 -872939 -872940 -872941 -872941 -872940 -872941 -872942 -872941 -872942 -872942 -872942 -872942 -872941 -872940 -872941 -872942 -872941 -872940 -872939 -872939 -872939 -872940 -872939 -872938 -872939 -872940 -87...
output:
-872884.0000000000
result:
ok found '-872884.00000', expected '-872884.00000', error '0.00000'
Test #18:
score: 0
Accepted
time: 10ms
memory: 3944kb
input:
100000 10 849531 849529 849531 849532 849532 849531 849530 849528 849526 849528 849530 849532 849531 849529 849529 849530 849532 849531 849529 849531 849532 849530 849532 849532 849531 849530 849528 849529 849529 849529 849531 849531 849530 849530 849530 849531 849532 849531 849530 849529 849531 849...
output:
849753.0000000000
result:
ok found '849753.00000', expected '849753.00000', error '0.00000'
Test #19:
score: 0
Accepted
time: 14ms
memory: 3800kb
input:
100000 1 -151199 -151192 -151196 -151186 -151185 -151188 -151198 -151198 -151192 -151187 -151190 -151192 -151188 -151182 -151179 -151181 -151184 -151190 -151190 -151180 -151175 -151165 -151163 -151154 -151159 -151162 -151169 -151177 -151172 -151180 -151180 -151170 -151173 -151182 -151181 -151188 -15...
output:
-149676.2222222222
result:
ok found '-149676.22222', expected '-149676.22222', error '-0.00000'
Test #20:
score: 0
Accepted
time: 14ms
memory: 3876kb
input:
100000 10 344590 344520 344431 344411 344387 344369 344276 344334 344339 344322 344357 344410 344454 344364 344353 344327 344324 344359 344402 344381 344290 344206 344166 344217 344284 344236 344137 344172 344120 344099 344016 344090 344033 344106 344185 344136 344081 344060 344026 344037 344099 344...
output:
345172.6535433071
result:
ok found '345172.65354', expected '345172.65354', error '0.00000'
Test #21:
score: 0
Accepted
time: 11ms
memory: 3876kb
input:
100000 100 -955168 -955172 -955178 -955179 -955178 -955181 -955177 -955175 -955165 -955165 -955164 -955156 -955152 -955159 -955153 -955145 -955138 -955144 -955134 -955134 -955137 -955132 -955139 -955134 -955134 -955142 -955134 -955144 -955151 -955161 -955151 -955155 -955164 -955165 -955175 -955179 -...
output:
-953521.4406779661
result:
ok found '-953521.44068', expected '-953521.44068', error '0.00000'
Test #22:
score: 0
Accepted
time: 14ms
memory: 3836kb
input:
100000 1000 622504 622593 621992 621299 622095 622342 622248 622134 622757 622122 621367 621508 620796 620171 619814 620186 621116 621038 621297 622045 622815 622294 622686 622235 623099 622135 621469 622259 622156 621652 620719 621530 621827 621494 621327 620415 620989 620535 620274 620179 619634 6...
output:
693530.6029339214
result:
ok found '693530.60293', expected '693530.60293', error '0.00000'
Test #23:
score: 0
Accepted
time: 11ms
memory: 3996kb
input:
100000 10000 981532 981522 981523 981518 981519 981509 981519 981524 981534 981534 981524 981531 981534 981534 981528 981524 981526 981521 981521 981529 981521 981516 981522 981515 981510 981500 981507 981502 981506 981515 981512 981506 981497 981498 981508 981500 981502 981494 981498 981488 981483 ...
output:
982613.0000000000
result:
ok found '982613.00000', expected '982613.00000', error '0.00000'
Test #24:
score: 0
Accepted
time: 16ms
memory: 4088kb
input:
100000 100000 -652734 -652643 -652726 -652700 -652787 -652721 -652656 -652613 -652662 -652647 -652605 -652559 -652505 -652510 -652531 -652610 -652663 -652587 -652671 -652770 -652860 -652763 -652722 -652772 -652801 -652735 -652712 -652638 -652676 -652590 -652569 -652598 -652592 -652674 -652737 -65279...
output:
-648765.0362339721
result:
ok found '-648765.03623', expected '-648765.03623', error '0.00000'
Test #25:
score: 0
Accepted
time: 14ms
memory: 3840kb
input:
100000 10 430315 429887 427376 432547 423789 417597 413547 414457 415656 423306 429519 424749 428176 420792 428310 424360 421261 430437 422820 418088 427712 420998 411577 403384 409262 401984 402949 408468 401262 402905 397622 397662 399534 399271 403217 400812 396927 399893 396404 402002 410729 402...
output:
996994.4316858079
result:
ok found '996994.43169', expected '996994.43169', error '0.00000'
Extra Test:
score: 0
Extra Test Passed