QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#178090 | #5377. $N$ 门问题 | zhoukangyang# | 35 | 8ms | 8260kb | C++11 | 1.9kb | 2023-09-13 17:55:52 | 2024-07-04 01:56:25 |
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 = (slv(f, 0) + slv(f, 1) * (n - 1)) / n;
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
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 1ms
memory: 7824kb
input:
1 2 3
output:
0.500000
result:
ok single line: '0.500000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7900kb
input:
1 3 5
output:
0.666667
result:
ok single line: '0.666667'
Test #3:
score: 0
Accepted
time: 0ms
memory: 8116kb
input:
1 4 5
output:
0.625000
result:
ok single line: '0.625000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 7728kb
input:
1 0 4
output:
error
result:
ok single line: 'error'
Test #5:
score: 0
Accepted
time: 1ms
memory: 7936kb
input:
1 1 3
output:
error
result:
ok single line: 'error'
Subtask #2:
score: 10
Accepted
Test #6:
score: 10
Accepted
time: 1ms
memory: 7700kb
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: 7836kb
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: 8116kb
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: 0ms
memory: 8124kb
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: 8016kb
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: 7896kb
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: 7680kb
input:
2 1000000007 1000000008 2 4
output:
error
result:
ok single line: 'error'
Test #13:
score: 0
Accepted
time: 0ms
memory: 7648kb
input:
3 0 1001 0 241221531 0 2
output:
error
result:
ok single line: 'error'
Test #14:
score: 0
Accepted
time: 1ms
memory: 7916kb
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: 0ms
memory: 7704kb
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: 7956kb
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: 1ms
memory: 7912kb
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: 1ms
memory: 7956kb
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: 1ms
memory: 7896kb
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: 1ms
memory: 7892kb
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: 1ms
memory: 7892kb
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: 1ms
memory: 7984kb
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: 7728kb
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: 7640kb
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: 7716kb
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: 0ms
memory: 7636kb
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: 7720kb
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: 1ms
memory: 7832kb
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: 7928kb
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: 7888kb
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: 1ms
memory: 7916kb
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: 7984kb
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: 0ms
memory: 8008kb
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: 7884kb
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: 1ms
memory: 8116kb
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: 1ms
memory: 7892kb
input:
1 5 6
output:
0.466667
result:
ok single line: '0.466667'
Test #37:
score: 0
Accepted
time: 1ms
memory: 7956kb
input:
1 6 7
output:
0.416667
result:
ok single line: '0.416667'
Test #38:
score: 0
Accepted
time: 0ms
memory: 7920kb
input:
1 7 8
output:
0.342857
result:
ok single line: '0.342857'
Test #39:
score: 0
Accepted
time: 0ms
memory: 8048kb
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: 7916kb
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: 8220kb
input:
3 0 2 0 5 1 3
output:
0.225000
result:
ok single line: '0.225000'
Test #42:
score: 0
Accepted
time: 0ms
memory: 7592kb
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: 1ms
memory: 7708kb
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: 7652kb
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: 7720kb
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: 7836kb
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: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Dependency #4:
100%
Accepted
Test #47:
score: 5
Accepted
time: 5ms
memory: 7916kb
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: 5ms
memory: 7880kb
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: 8ms
memory: 8260kb
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: 8ms
memory: 8056kb
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: -5
Time Limit Exceeded
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:
result:
Subtask #6:
score: 0
Wrong Answer
Test #57:
score: 0
Wrong Answer
time: 0ms
memory: 7928kb
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:
0%