QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#297977 | #958. Lockout vs tourist | Hunster | RE | 1275ms | 69324kb | C++23 | 957b | 2024-01-05 15:12:55 | 2024-01-05 15:12:56 |
Judging History
answer
#include <bits/stdc++.h>
using LD = long double;
int n;
int w[22];
LD f[1 << 22];
LD work(int mask) {
const int t = __builtin_popcount(mask);
if (t <= 1) return 0;
std::vector<LD> a, b;
for (int i = 0; i < n; i++)
if (mask >> i & 1) {
a.push_back(w[i]);
b.push_back(f[mask ^ (1 << i)]);
}
assert(a[0] > b[0]);
LD sump = 0, k = 1 / (a[0] - b[0]);
for (int i = 1; i < t; i++) {
LD del = (a[i - 1] - a[i]) * k;
if (sump + del > 1) return a[i - 1] - (1 - sump) / k;
sump += del;
k += 1 / (a[i] - b[i]);
}
return a[t - 1] - (1 - sump) / k;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &w[i]);
std::sort(w, w + n, [](int x, int y) { return x > y; });
for (int mask = 0; mask < 1 << n; mask++) f[mask] = work(mask);
printf("%.10Lf\n", f[(1 << n) - 1]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3680kb
input:
2 6 7
output:
3.2307692308
result:
ok found '3.2307692', expected '3.2307692', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
3 1 1 1
output:
0.8333333333
result:
ok found '0.8333333', expected '0.8333333', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
11 1 2 3 4 5 6 7 8 9 10 11
output:
9.4422713866
result:
ok found '9.4422714', expected '9.4422714', error '0.0000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3740kb
input:
2 1 1000000000
output:
0.9999999990
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
5 76 57 68 36 63
output:
63.3539651124
result:
ok found '63.3539651', expected '63.3539651', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
10 550060 445055 787034 728427 572554 894096 875473 622886 575460 119034
output:
818911.3739286328
result:
ok found '818911.3739286', expected '818911.3739286', error '0.0000000'
Test #7:
score: 0
Accepted
time: 9ms
memory: 4304kb
input:
15 10 8 9 6 9 5 3 9 7 8 7 6 7 10 7
output:
9.4986796318
result:
ok found '9.4986796', expected '9.4986796', error '0.0000000'
Test #8:
score: 0
Accepted
time: 305ms
memory: 20060kb
input:
20 3 2 2 1 2 3 1 3 3 2 1 2 3 2 3 2 3 1 3 1
output:
2.9999751984
result:
ok found '2.9999752', expected '2.9999752', error '0.0000000'
Test #9:
score: 0
Accepted
time: 613ms
memory: 36456kb
input:
21 608646711 538679781 175667175 596079164 43084965 174585378 46825084 647100103 820432909 254925688 469580725 888475497 802835182 554123188 53822453 849477025 715668397 194908968 407987651 349577139 457598738
output:
831669480.2821692052
result:
ok found '831669480.2821692', expected '831669480.2821692', error '0.0000000'
Test #10:
score: 0
Accepted
time: 1268ms
memory: 69324kb
input:
22 593316975 268451765 664075355 817013319 325389147 553878522 663160635 289932897 995002446 771863307 252061346 171723220 102306933 722521207 52895206 996540774 335816175 415049181 629862034 371890996 327908946 357122932
output:
899795716.3481486386
result:
ok found '899795716.3481486', expected '899795716.3481486', error '0.0000000'
Test #11:
score: 0
Accepted
time: 1250ms
memory: 69276kb
input:
22 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152
output:
895851.5340571190
result:
ok found '895851.5340571', expected '895851.5340571', error '0.0000000'
Test #12:
score: 0
Accepted
time: 1275ms
memory: 69268kb
input:
22 1000001 1000002 1000003 1000004 1000005 1000006 1000007 1000008 1000009 1000010 1000011 1000012 1000013 1000014 1000015 1000016 1000017 1000018 1000019 1000020 1000021 1000022
output:
1000020.4421252878
result:
ok found '1000020.4421253', expected '1000020.4421253', error '0.0000000'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
10 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
output:
999999724.4268077601
result:
ok found '999999724.4268078', expected '999999724.4268078', error '0.0000000'
Test #14:
score: -100
Runtime Error
input:
22 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000