QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#178100 | #5377. $N$ 门问题 | zhoukangyang# | 40 | 13ms | 12468kb | C++11 | 1.9kb | 2023-09-13 17:58:34 | 2024-07-04 01:56:29 |
Judging History
answer
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define ull unsigned long long
#define sz(a) ((int) a.size())
#define vi vector<int>
#define me(a, x) memset(a, x, sizeof(a))
using namespace std;
const int N = 1 << 21, L = 5e5, mod = 998244353;
double f[N];
ll n;
int k;
ll a[N], b[N];
ll rd() {
cin >> k;
L(i, 1, k) {
cin >> a[i] >> b[i];
}
n = 0;
while(true) {
int win = 1;
L(i, 1, k) {
if(n % b[i] != a[i]) {
win = 0;
break;
}
}
if(win) break;
++n;
if(n > 200) {
n = 0;
break;
}
}
return n;
}
map < vector < double >, double > MP[10];
double slv(vector < double > a, int cur) {
if(sz(a) == 2) {
return cur == 0;
}
if(cur > 1)
swap(a[1], a[cur]), cur = 1;
sort(a.begin() + 2, a.end());
if(MP[cur].count(a)) return MP[cur][a];
double win = 1;
L(p, 1, sz(a) - 1) if(p != cur) {
double sum1 = 0, sum2 = 0;
L(i, 0, sz(a) - 1) if(i != cur) {
sum1 += a[i];
if(i != p) sum2 += a[i];
}
sum1 /= sum2;
vector < double > b;
L(i, 0, sz(a) - 1) {
if(i == cur) b.emplace_back(a[i]);
else if(i != p) b.emplace_back(a[i] * sum1);
}
double mx = 0;
L(i, 0, sz(b) - 1) {
mx = max(mx, b[i]);
}
int total = 0;
double sum = 0;
L(i, 0, sz(b) - 1) {
if(fabs(b[i] - mx) <= 1e-9) {
total += 1;
sum += slv(b, i);
}
}
sum /= total;
win = min(win, sum);
}
return MP[cur][a] = win;
}
int main () {
ios :: sync_with_stdio(false);
cin.tie (0); cout.tie (0);
n = rd();
if(n < 2) {
cout << "error\n";
return 0;
}
vector < double > f(n);
L(i, 0, n - 1) {
f[i] = 1;
}
double ans = n < 13 ? (slv(f, 0) + slv(f, 1) * (n - 1)) / n : 0;
cout.precision(6); cout << fixed;
cout << ans << '\n';
return 0;
}
/*
(n-1)/(n-2) 1 [(n-1)/(n-2)] (n-1)/(n-2) (n-1)/(n-2) x
*/
詳細信息
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 1ms
memory: 7924kb
input:
1 2 3
output:
0.500000
result:
ok single line: '0.500000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 8084kb
input:
1 3 5
output:
0.666667
result:
ok single line: '0.666667'
Test #3:
score: 0
Accepted
time: 1ms
memory: 8152kb
input:
1 4 5
output:
0.625000
result:
ok single line: '0.625000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 7928kb
input:
1 0 4
output:
error
result:
ok single line: 'error'
Test #5:
score: 0
Accepted
time: 0ms
memory: 7728kb
input:
1 1 3
output:
error
result:
ok single line: 'error'
Subtask #2:
score: 10
Accepted
Test #6:
score: 10
Accepted
time: 1ms
memory: 7924kb
input:
8 1 160005726539569 1 233 0 1 1 2947295521 1 686719856393 1 54289 1 12649337 1 37281334283719577
output:
error
result:
ok single line: 'error'
Test #7:
score: 0
Accepted
time: 1ms
memory: 7920kb
input:
10 2 64 0 2 2 512 2 4 2 32 2 16 2 256 0 1 2 8 2 128
output:
0.500000
result:
ok single line: '0.500000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 7924kb
input:
10 3 256 3 16 0 1 3 8 3 512 3 32 3 4 3 128 3 64 1 2
output:
0.666667
result:
ok single line: '0.666667'
Test #9:
score: 0
Accepted
time: 1ms
memory: 8020kb
input:
10 0 2 4 8 0 4 4 256 0 1 4 512 4 32 4 128 4 64 4 16
output:
0.625000
result:
ok single line: '0.625000'
Test #10:
score: 0
Accepted
time: 1ms
memory: 7928kb
input:
10 5 128 5 32 5 16 1 4 0 1 5 64 5 256 5 512 1 2 5 8
output:
0.466667
result:
ok single line: '0.466667'
Test #11:
score: 0
Accepted
time: 0ms
memory: 7928kb
input:
10 6 32 6 16 6 256 6 64 0 1 6 128 0 2 6 512 6 8 2 4
output:
0.416667
result:
ok single line: '0.416667'
Test #12:
score: 0
Accepted
time: 1ms
memory: 7924kb
input:
2 1000000007 1000000008 2 4
output:
error
result:
ok single line: 'error'
Test #13:
score: 0
Accepted
time: 1ms
memory: 7608kb
input:
3 0 1001 0 241221531 0 2
output:
error
result:
ok single line: 'error'
Test #14:
score: 0
Accepted
time: 1ms
memory: 7924kb
input:
3 6 1001 6 241221531 0 2
output:
0.416667
result:
ok single line: '0.416667'
Subtask #3:
score: 10
Accepted
Dependency #2:
100%
Accepted
Test #15:
score: 10
Accepted
time: 1ms
memory: 7592kb
input:
8 1 160005726539569 1 233 0 1 1 2947295521 1 686719856393 1 54289 1 12649337 1 37281334283719577
output:
error
result:
ok single line: 'error'
Test #16:
score: 0
Accepted
time: 1ms
memory: 7928kb
input:
10 2 64 0 2 2 512 2 4 2 32 2 16 2 256 0 1 2 8 2 128
output:
0.500000
result:
ok single line: '0.500000'
Test #17:
score: 0
Accepted
time: 0ms
memory: 8084kb
input:
10 3 256 3 16 0 1 3 8 3 512 3 32 3 4 3 128 3 64 1 2
output:
0.666667
result:
ok single line: '0.666667'
Test #18:
score: 0
Accepted
time: 0ms
memory: 7928kb
input:
10 0 2 4 8 0 4 4 256 0 1 4 512 4 32 4 128 4 64 4 16
output:
0.625000
result:
ok single line: '0.625000'
Test #19:
score: 0
Accepted
time: 0ms
memory: 8160kb
input:
10 5 128 5 32 5 16 1 4 0 1 5 64 5 256 5 512 1 2 5 8
output:
0.466667
result:
ok single line: '0.466667'
Test #20:
score: 0
Accepted
time: 0ms
memory: 7864kb
input:
10 6 32 6 16 6 256 6 64 0 1 6 128 0 2 6 512 6 8 2 4
output:
0.416667
result:
ok single line: '0.416667'
Test #21:
score: 0
Accepted
time: 0ms
memory: 8160kb
input:
10 7 16 7 8 3 4 0 1 7 32 7 256 7 64 1 2 7 512 7 128
output:
0.342857
result:
ok single line: '0.342857'
Test #22:
score: 0
Accepted
time: 2ms
memory: 7948kb
input:
10 8 16 8 64 8 32 0 1 0 8 0 2 8 128 0 4 8 256 8 512
output:
0.291667
result:
ok single line: '0.291667'
Test #23:
score: 0
Accepted
time: 0ms
memory: 7964kb
input:
10 1 2 113 128 0 8 1 16 49 64 17 32 241 256 1 4 241 512 0 1
output:
error
result:
ok single line: 'error'
Test #24:
score: 0
Accepted
time: 0ms
memory: 7660kb
input:
10 5 8 237 512 1 2 13 32 12 16 0 1 109 128 1 4 45 64 237 256
output:
error
result:
ok single line: 'error'
Test #25:
score: 0
Accepted
time: 1ms
memory: 7708kb
input:
10 11 16 43 64 235 512 11 32 3 4 0 1 235 256 0 2 107 128 3 8
output:
error
result:
ok single line: 'error'
Test #26:
score: 0
Accepted
time: 1ms
memory: 7920kb
input:
10 9 32 1 2 41 64 233 512 233 256 1 4 0 1 9 16 1 8 115 128
output:
error
result:
ok single line: 'error'
Subtask #4:
score: 10
Accepted
Dependency #3:
100%
Accepted
Test #27:
score: 10
Accepted
time: 1ms
memory: 7764kb
input:
8 1 5 1 15 1 2 1 30 1 3 0 1 1 6 1 10
output:
error
result:
ok single line: 'error'
Test #28:
score: 0
Accepted
time: 0ms
memory: 7860kb
input:
8 2 30 2 15 0 1 2 6 2 5 2 3 2 10 0 2
output:
0.500000
result:
ok single line: '0.500000'
Test #29:
score: 0
Accepted
time: 1ms
memory: 7672kb
input:
8 0 1 0 3 0 15 0 2 0 30 0 6 0 5 0 10
output:
error
result:
ok single line: 'error'
Test #30:
score: 0
Accepted
time: 1ms
memory: 7924kb
input:
8 1 2 5 30 0 1 0 5 2 3 5 6 5 15 5 10
output:
0.466667
result:
ok single line: '0.466667'
Test #31:
score: 0
Accepted
time: 0ms
memory: 7936kb
input:
8 3 5 0 3 3 15 3 10 0 1 1 2 3 30 3 6
output:
0.666667
result:
ok single line: '0.666667'
Test #32:
score: 0
Accepted
time: 0ms
memory: 7916kb
input:
6 0 3 3 4 1 2 3 6 0 1 3 12
output:
0.666667
result:
ok single line: '0.666667'
Test #33:
score: 0
Accepted
time: 1ms
memory: 7896kb
input:
6 0 1 2 6 0 4 2 3 0 2 8 12
output:
0.291667
result:
ok single line: '0.291667'
Test #34:
score: 0
Accepted
time: 1ms
memory: 7860kb
input:
6 0 1 1 2 2 3 1 4 5 6 5 12
output:
0.466667
result:
ok single line: '0.466667'
Test #35:
score: 0
Accepted
time: 0ms
memory: 7932kb
input:
6 3 12 1 2 0 3 0 1 3 4 3 6
output:
0.666667
result:
ok single line: '0.666667'
Test #36:
score: 0
Accepted
time: 2ms
memory: 8152kb
input:
1 5 6
output:
0.466667
result:
ok single line: '0.466667'
Test #37:
score: 0
Accepted
time: 1ms
memory: 8160kb
input:
1 6 7
output:
0.416667
result:
ok single line: '0.416667'
Test #38:
score: 0
Accepted
time: 1ms
memory: 7932kb
input:
1 7 8
output:
0.342857
result:
ok single line: '0.342857'
Test #39:
score: 0
Accepted
time: 1ms
memory: 7888kb
input:
4 0 2 0 4 2 3 3 5
output:
0.291667
result:
ok single line: '0.291667'
Test #40:
score: 0
Accepted
time: 2ms
memory: 8260kb
input:
4 0 3 0 9 1 2 4 5
output:
0.253968
result:
ok single line: '0.253968'
Test #41:
score: 0
Accepted
time: 0ms
memory: 8376kb
input:
3 0 2 0 5 1 3
output:
0.225000
result:
ok single line: '0.225000'
Test #42:
score: 0
Accepted
time: 1ms
memory: 7612kb
input:
6 0 1 0 2 0 6 0 12 0 4 0 3
output:
error
result:
ok single line: 'error'
Test #43:
score: 0
Accepted
time: 0ms
memory: 7964kb
input:
6 837250 1574381 22682 54289 20 29 81 233 6139 6757 0 1
output:
error
result:
ok single line: 'error'
Test #44:
score: 0
Accepted
time: 1ms
memory: 7704kb
input:
6 12521 54289 1478324 1574381 20 29 171 233 0 1 5298 6757
output:
error
result:
ok single line: 'error'
Test #45:
score: 0
Accepted
time: 1ms
memory: 7664kb
input:
8 9430402 12649337 193 233 12831718919798818 37281334283719577 358403095623 686719856393 31260796633308 160005726539569 0 1 38405 54289 1780337582 2947295521
output:
error
result:
ok single line: 'error'
Test #46:
score: 0
Accepted
time: 1ms
memory: 8164kb
input:
8 0 2 6 30 0 1 1 5 0 3 0 6 6 15 6 10
output:
0.416667
result:
ok single line: '0.416667'
Subtask #5:
score: 5
Accepted
Dependency #1:
100%
Accepted
Dependency #4:
100%
Accepted
Test #47:
score: 5
Accepted
time: 4ms
memory: 8104kb
input:
27216 1100249873 1253754216 25197605440 29192187024 1744207706249 2277822821274 12223300097 26875346784 147492353 275539264 320696949581 377638144884 419900489 699380136 453032 1231659 266587329 890393504 7730812097 11914078176 524332817 661404744 2287601 8261694 1156980833 14524544034 967031297 145...
output:
error
result:
ok single line: 'error'
Test #48:
score: 0
Accepted
time: 4ms
memory: 7948kb
input:
27216 1887302 8343192 98702 115368 3405075396542 142252321079232 3015286 10958948 59487416 481578669 1045054 3865664 72754046 23575685952 370699174 794635556 163774430 446662944 10742784326 36887818968 2588314 130307788 1814817881150 2290728087648 59263478 81513432 105993323864 106600637682 27086905...
output:
error
result:
ok single line: 'error'
Test #49:
score: 0
Accepted
time: 13ms
memory: 8128kb
input:
50000 13191867 17093160 20006787 28265160 531754947 696215520 49540995 227505696 1073316627 1706292720 58569507 194230400 51790622607 214521407100 141120675 500919552 1207143507 1366149400 1382307 4379200 850756707 11479406400 453052323 1743565824 850756707 2203118400 231422833827 322489324080 15091...
output:
error
result:
ok single line: 'error'
Test #50:
score: 0
Accepted
time: 10ms
memory: 8064kb
input:
50000 9122968989 10897286400 1244648539 11099963875 1895367069 2400239520 35685693 52442208 3724120989 59434502400 6070719789 13899085200 8432349 39225120 131925789 306153000 101446557 226417152 2483743030749 3009900358080 13965142941 24139551744 30294839709 75157175808 317618589 535307520 39789 188...
output:
error
result:
ok single line: 'error'
Test #51:
score: 0
Accepted
time: 8ms
memory: 8252kb
input:
50000 194 83566560 194 11970504 194 3351600 194 56073378816 194 157815216 194 2336202000 194 17749670400 194 2299884678 194 2366622720 194 4135131000 194 26409240 194 13248000 194 83847224260800 194 325909584 194 6051302400 194 1944746496 194 146024424000 194 1574773200 194 2472371200 194 2351661312...
output:
0.000000
result:
ok single line: '0.000000'
Test #52:
score: 0
Accepted
time: 7ms
memory: 8356kb
input:
50000 44 736736000 44 50798720 44 22011 44 10423897344 44 120011976 44 2904720 44 50400 44 608 44 2019025008000 44 885248 44 290811628800 44 5040734899200 44 147784000 44 17634412800 44 141099678720 44 15558400 44 20286 44 20860632 44 397555200 44 12926460 44 21042028800 44 1543082112 44 49024500 44...
output:
0.000000
result:
ok single line: '0.000000'
Test #53:
score: 0
Accepted
time: 8ms
memory: 12468kb
input:
50000 134 19132344 134 98394912000 134 118503000 134 515982918528000 134 1003701600 134 17564778000 134 54725461056000 134 607733280 134 1926144 134 375921000 134 506177100 134 728377920 134 3353275800 134 242181030 134 8398 134 11286912 134 1771619850 134 1302013440 134 20155582755 134 473211847680...
output:
0.000000
result:
ok single line: '0.000000'
Test #54:
score: 0
Accepted
time: 7ms
memory: 8444kb
input:
50000 4 36679578624 4 761177088 4 15810163200 4 3086022240 4 474249006 4 46986240 4 2096760960 4 2409402996 4 4717024 4 51919795200 4 870870 4 41146963200 4 3064591530 4 3516307200 4 64700052480 4 8061768000 4 21621600 4 38085120 4 30111048000 4 91423987200 4 10585935360 4 303688 4 6974813664000 4 3...
output:
0.625000
result:
ok single line: '0.625000'
Test #55:
score: 0
Accepted
time: 7ms
memory: 8412kb
input:
50000 5 584050500 5 21810872160 5 1201200 5 520608000 5 16052801909760 5 42730688000 5 8540588160 5 271591320 5 2688940800 5 13596128 5 89226295200 5 128012774400 5 2660486400 5 168814800 5 3304324108800 5 1927522396800 5 2565255987 5 26999000 5 437184 5 182656500 5 26096241600 5 617204448000 5 9335...
output:
0.466667
result:
ok single line: '0.466667'
Test #56:
score: 0
Accepted
time: 11ms
memory: 8024kb
input:
50000 81 153830476800 81 18712512 81 113622372864 81 2457061516800 81 48456600192000 81 78450240 81 174730080 81 552484800 81 760864104000 81 70259112 81 2134080 81 490416585750 81 22207185 81 2142201600 81 5852000 81 173974944000 81 6359661000 81 4258128 81 29044915200 81 259930944 81 19673280 81 1...
output:
error
result:
ok single line: 'error'
Subtask #6:
score: 0
Wrong Answer
Test #57:
score: 0
Wrong Answer
time: 2ms
memory: 7668kb
input:
15 15 17 2 3 5 31 4 5 12 29 38 41 3 11 44 47 16 23 11 19 6 13 3 37 1 2 21 43 5 7
output:
error
result:
wrong answer 1st lines differ - expected: '0.000000', found: 'error'
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
0%