QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#672504 | #2878. Journey in Fog | IllusionaryDominance# | WA | 67ms | 14408kb | C++20 | 2.1kb | 2024-10-24 17:06:28 | 2024-10-24 17:06:30 |
Judging History
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'