QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#178108 | #5377. $N$ 门问题 | zhoukangyang# | 60 | 10ms | 8640kb | C++11 | 2.1kb | 2023-09-13 18:01:48 | 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];
}
ll lcm = 1;
int top = 0;
L(i, 1, k) {
L(j, 1, top) {
ll gc = __gcd(b[i], b[j]);
if(a[i] % gc != a[j] % gc) {
return -1;
}
}
if(lcm % b[i]) {
++top;
a[top] = a[i];
b[top] = 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) {
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 < 12 ? (slv(f, 0) + slv(f, 1) * (n - 1)) / n : 0;
cout.precision(6); cout << fixed;
cout << ans << '\n';
return 0;
}
详细
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 1ms
memory: 8064kb
input:
1 2 3
output:
0.500000
result:
ok single line: '0.500000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7944kb
input:
1 3 5
output:
0.666667
result:
ok single line: '0.666667'
Test #3:
score: 0
Accepted
time: 1ms
memory: 7908kb
input:
1 4 5
output:
0.625000
result:
ok single line: '0.625000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 7656kb
input:
1 0 4
output:
error
result:
ok single line: 'error'
Test #5:
score: 0
Accepted
time: 1ms
memory: 7916kb
input:
1 1 3
output:
error
result:
ok single line: 'error'
Subtask #2:
score: 10
Accepted
Test #6:
score: 10
Accepted
time: 1ms
memory: 7940kb
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: 7852kb
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: 1ms
memory: 7948kb
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: 8012kb
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: 0ms
memory: 7908kb
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: 1ms
memory: 7904kb
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: 0ms
memory: 7716kb
input:
2 1000000007 1000000008 2 4
output:
error
result:
ok single line: 'error'
Test #13:
score: 0
Accepted
time: 1ms
memory: 7580kb
input:
3 0 1001 0 241221531 0 2
output:
error
result:
ok single line: 'error'
Test #14:
score: 0
Accepted
time: 0ms
memory: 8144kb
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: 7776kb
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: 8004kb
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: 8044kb
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: 7904kb
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: 8040kb
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: 8072kb
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: 7952kb
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: 8056kb
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: 1ms
memory: 7656kb
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: 1ms
memory: 7656kb
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: 1ms
memory: 7656kb
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: 7728kb
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: 7908kb
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: 7912kb
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: 8136kb
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: 8008kb
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: 1ms
memory: 8008kb
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: 7928kb
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: 7924kb
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: 7916kb
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: 0ms
memory: 8140kb
input:
1 5 6
output:
0.466667
result:
ok single line: '0.466667'
Test #37:
score: 0
Accepted
time: 0ms
memory: 7912kb
input:
1 6 7
output:
0.416667
result:
ok single line: '0.416667'
Test #38:
score: 0
Accepted
time: 0ms
memory: 8152kb
input:
1 7 8
output:
0.342857
result:
ok single line: '0.342857'
Test #39:
score: 0
Accepted
time: 0ms
memory: 7936kb
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: 0ms
memory: 8120kb
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: 2ms
memory: 8240kb
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: 7908kb
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: 7912kb
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: 7912kb
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: 7712kb
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: 8056kb
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: 4ms
memory: 7928kb
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: -5
Time Limit Exceeded
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:
result:
Subtask #6:
score: 25
Accepted
Test #57:
score: 25
Accepted
time: 0ms
memory: 8040kb
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:
0.000000
result:
ok single line: '0.000000'
Test #58:
score: 0
Accepted
time: 1ms
memory: 7912kb
input:
14 10 16 21 37 0 23 0 5 11 17 1 3 17 29 19 31 33 43 6 13 4 7 16 41 9 19 0 11
output:
0.000000
result:
ok single line: '0.000000'
Test #59:
score: 0
Accepted
time: 1ms
memory: 7848kb
input:
14 7 23 2 16 2 19 9 11 2 5 7 13 2 7 25 41 25 31 3 9 7 43 3 37 8 17 9 29
output:
0.000000
result:
ok single line: '0.000000'
Test #60:
score: 0
Accepted
time: 1ms
memory: 8136kb
input:
14 2 13 14 19 38 43 10 17 3 8 21 29 0 9 4 7 2 5 1 37 2 11 5 23 22 31 10 41
output:
0.000000
result:
ok single line: '0.000000'
Test #61:
score: 0
Accepted
time: 1ms
memory: 7852kb
input:
2 543380932 999999999 451172165 1000000000
output:
0.000000
result:
ok single line: '0.000000'
Test #62:
score: 0
Accepted
time: 1ms
memory: 7852kb
input:
15 1 2 9 13 31 37 1 17 0 23 1 3 2 5 17 31 9 11 5 29 4 47 6 7 40 41 1 19 26 43
output:
0.000000
result:
ok single line: '0.000000'
Test #63:
score: 0
Accepted
time: 7ms
memory: 8340kb
input:
50000 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 ...
output:
0.000000
result:
ok single line: '0.000000'
Test #64:
score: 0
Accepted
time: 8ms
memory: 8308kb
input:
50000 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 ...
output:
0.000000
result:
ok single line: '0.000000'
Test #65:
score: 0
Accepted
time: 4ms
memory: 8108kb
input:
50000 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 ...
output:
error
result:
ok single line: 'error'
Test #66:
score: 0
Accepted
time: 10ms
memory: 8304kb
input:
50000 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 ...
output:
error
result:
ok single line: 'error'
Test #67:
score: 0
Accepted
time: 7ms
memory: 8640kb
input:
50000 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 ...
output:
0.225000
result:
ok single line: '0.225000'
Test #68:
score: 0
Accepted
time: 8ms
memory: 8336kb
input:
50000 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 ...
output:
0.253968
result:
ok single line: '0.253968'
Test #69:
score: 0
Accepted
time: 1ms
memory: 7948kb
input:
3 0 1 1 707185547 1 1000000000
output:
error
result:
ok single line: '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%