QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#672504#2878. Journey in FogIllusionaryDominance#WA 67ms14408kbC++202.1kb2024-10-24 17:06:282024-10-24 17:06:30

Judging History

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

  • [2024-10-24 17:06:30]
  • 评测
  • 测评结果:WA
  • 用时:67ms
  • 内存:14408kb
  • [2024-10-24 17:06:28]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000 + 5;

int N, M, L, V, v[MAX_N];
double t1[MAX_N], t2[MAX_N], suf[MAX_N];
pair <double, int> event[MAX_N << 1], tmp1[MAX_N], tmp2[MAX_N];

double solve(int n, double t) {
    double cur = 0;
    int sz1 = 0, sz2 = 0;
    static double t1[MAX_N], t2[MAX_N];
    for (int i = n; i > 0; i --) {
        t1[i] = (L - v[i] * t) / (double)v[i];
        t2[i] = 2.0 * (L - v[i] * t) / (v[i] + V);
        cur += t1[i];
        tmp1[++ sz1] = pair((L - v[i] * t) / (v[i] + V), i);
        if (v[i] > V) tmp2[++ sz2] = pair(0.5 * (L - v[i] * t) / v[i], -i);
    }
    M = sz1 + sz2;
    for (int i = 1, j = 1, k = 1; i <= M; i ++) {
        if (k > sz2 || (j <= sz1 && tmp1[j].first < tmp2[k].first)) event[i] = tmp1[j ++];
        else event[i] = tmp2[k ++];
    }
    double ans = cur;
    int cnt = 0;
    for (int i = 1; i <= M; i ++) {
        auto [t0, pos] = event[i];
        if (pos < 0) {
            cnt ++;
            cur -= t1[-pos];
        }else {
            if (v[pos] > V) {
                cnt --;
            }else {
                cur -= t1[pos];
            }
            cur += t2[pos];
        }
        ans = min(ans, cur + 2.0 * cnt * t0);
    }
    return ans + t * n;
}

int main() {
    scanf("%d%d%d", &N, &L, &V);
    for (int i = 1; i <= N; i ++) {
        scanf("%d", v + i);
        t1[i] = (double)L / (double)v[i];
        t2[i] = 2.0 * L / (v[i] + V);
    }
    for (int i = N; i > 0; i --) suf[i] = suf[i + 1] + t1[i];
    int l = 1, r = N - 1;
    double ans = solve(N, 0);
    while (r - l > 1) {
        int mid1 = (l * 2 + r) / 3, mid2 = (l + r * 2 + 1) / 3;
        double res1 = solve(mid1, t1[mid1 + 1]) + suf[mid1 + 1];
        double res2 = solve(mid2, t1[mid2 + 1]) + suf[mid2 + 1];
        if (res1 < res2) {
            r = mid2 - 1;
            ans = min(ans, res1);
        }else {
            l = mid2 + 1;
            ans = min(ans, res2);
        }
    }
    for (int i = l; i <= r; i ++) ans = min(ans, solve(i, t1[i + 1]) + suf[i + 1]);
    printf("%.10lf\n", ans / N);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 10084kb

input:

1 1000 30
10

output:

50.0000000000

result:

ok found '50.000000000', expected '50.000000000', error '0.000000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 10088kb

input:

1 1000 10
30

output:

33.3333333333

result:

ok found '33.333333333', expected '33.333333333', error '0.000000000'

Test #3:

score: 0
Accepted
time: 1ms
memory: 12064kb

input:

4 1000 20
10 20 30 40

output:

46.2500000000

result:

ok found '46.250000000', expected '46.250000000', error '0.000000000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 10024kb

input:

2 68 7
4 9

output:

10.4318181818

result:

ok found '10.431818182', expected '10.431818182', error '0.000000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 12124kb

input:

5 636 86
41 48 59 80 83

output:

8.6939953919

result:

ok found '8.693995392', expected '8.693995392', error '0.000000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 12060kb

input:

10 14292 401
28 74 253 272 338 692 751 770 803 909

output:

37.2599434994

result:

ok found '37.259943499', expected '37.259943499', error '0.000000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 12056kb

input:

10 456181726 218016
136026 204990 312262 507994 650490 760622 777222 811022 814221 915133

output:

1093.7615490599

result:

ok found '1093.761549060', expected '1093.761549060', error '0.000000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 10092kb

input:

100 740855572 627893
7447 16238 19397 19431 22315 34974 40661 63794 67348 76727 101237 111777 124380 134888 158793 168304 170527 180211 185231 186691 197733 216296 220443 222434 223320 224646 233183 238089 242665 244435 253479 266808 268518 276772 280350 280535 292232 296126 300003 309785 310954 311...

output:

1458.9933491043

result:

ok found '1458.993349104', expected '1458.993349104', error '0.000000000'

Test #9:

score: 0
Accepted
time: 1ms
memory: 10100kb

input:

1000 431318978 860594
906 4043 4719 4921 5620 6679 7464 7826 8518 8766 10595 11382 11937 12418 13403 14845 15351 16232 16254 16841 17210 17266 17472 17780 20673 21115 23940 24358 25141 25656 25837 27916 30857 31008 32458 33103 33643 36200 36552 37191 39425 40653 41040 42070 44272 47475 50050 50894 5...

output:

666.8414493254

result:

ok found '666.841449325', expected '666.841449325', error '0.000000000'

Test #10:

score: 0
Accepted
time: 4ms
memory: 10272kb

input:

10000 761728855 434871
43 115 264 778 860 869 907 920 954 973 1075 1162 1166 1282 1615 1629 1682 1940 2020 2081 2167 2171 2289 2517 2611 2615 2823 2840 2843 2938 2963 3023 3039 3191 3266 3281 3289 3477 3574 3588 3595 3605 3857 3881 3951 4160 4553 4668 4683 4752 4766 4800 4843 5032 5074 5082 5623 576...

output:

1824.9531588890

result:

ok found '1824.953158889', expected '1824.953158889', error '0.000000000'

Test #11:

score: 0
Accepted
time: 36ms
memory: 14408kb

input:

100000 289994260 450063
3 22 25 37 58 63 74 77 93 94 100 101 109 116 123 147 149 157 163 167 169 182 203 224 228 243 246 254 263 279 282 292 297 311 354 378 381 388 398 400 429 431 441 442 444 466 477 478 486 488 513 517 520 539 581 584 586 594 600 622 628 631 681 690 700 711 721 734 736 738 739 807...

output:

678.2588043580

result:

ok found '678.258804358', expected '678.258804358', error '0.000000000'

Test #12:

score: 0
Accepted
time: 37ms
memory: 14384kb

input:

100000 492644850 414710
21 23 32 36 48 50 59 68 83 85 119 120 127 131 142 146 155 172 181 187 191 207 225 230 254 256 306 342 347 362 364 367 386 390 392 407 429 445 447 456 461 482 489 496 524 531 564 570 590 610 615 623 643 657 667 671 686 692 699 702 706 707 716 731 737 738 746 776 778 782 785 79...

output:

1207.5858944580

result:

ok found '1207.585894458', expected '1207.585894458', error '0.000000000'

Test #13:

score: -100
Wrong Answer
time: 67ms
memory: 14384kb

input:

100000 891103720 283167
4 14 25 35 40 45 80 83 95 104 109 122 127 146 147 152 187 193 210 212 215 220 234 277 284 311 318 324 331 337 340 342 343 345 346 362 364 365 370 372 377 384 395 399 401 424 427 430 441 454 460 481 483 491 492 496 504 513 514 522 540 548 558 572 575 581 599 611 654 665 670 73...

output:

2526.0453863802

result:

wrong answer 1st numbers differ - expected: '2526.0403612', found: '2526.0453864', error = '0.0000020'