QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#578854#9264. Minimax Limitucup-team004#AC ✓469ms6740kbC++203.1kb2024-09-20 21:56:082024-09-20 21:56:08

Judging History

你现在查看的是最新测评结果

  • [2024-09-20 21:56:08]
  • 评测
  • 测评结果:AC
  • 用时:469ms
  • 内存:6740kb
  • [2024-09-20 21:56:08]
  • 提交

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