QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#575425 | #5377. $N$ 门问题 | 0000pnc | 35 | 9ms | 5324kb | C++14 | 3.6kb | 2024-09-19 14:10:54 | 2024-09-19 14:10:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef __int128_t LL;
void write(LL x, char ed) {
if (x >= 10) write(x / 10, 0);
putchar(x % 10 + '0');
if (ed) putchar(ed);
}
struct Frac {
LL p, q;
Frac() {}
Frac(LL x, LL y) { LL g = __gcd(x, y); p = x / g, q = y / g; }
Frac operator* (Frac y) {
LL g = __gcd(q * y.q, p * y.p);
return Frac(p * y.p / g, q * y.q / g);
}
Frac operator+ (Frac y) {
LL g = __gcd(p * y.q + q * y.p, q * y.q);
return Frac((p * y.q + q * y.p) / g, q * y.q / g);
}
bool operator< (Frac y) {
return p * y.q < q * y.p;
}
bool operator> (Frac y) {
return y < (*this);
}
bool operator== (Frac y) {
return !(((*this) < y) || (y < (*this)));
}
bool operator!= (Frac y) {
return !((*this) == y);
}
void operator+= (Frac y) { (*this) = (*this) + y; }
void operator*= (Frac y) { (*this) = (*this) * y; }
double val() { if (q == 0) return 1e18; return (double)1. * p / q; }
};
Frac min(Frac x, Frac y) { return x < y ? x : y; }
Frac max(Frac x, Frac y) { return x > y ? x : y; }
LL n, T;
LL num[50005][2];
Frac dfs(vector<LL> now, int lev, Frac pro) {
if (now.size() == 2) return Frac((now[0] > now[1]) + (now[0] >= now[1]), 2) * pro;
LL mx = 0; vector<int> mxp;
for (int i = 0; i < now.size(); i++) mx = max(mx, now[i]);
for (int i = 0; i < now.size(); i++) if (now[i] == mx) mxp.push_back(i);
Frac res(0, 1);
if (mxp[0] == 0) {
vector<LL> tmp; Frac mn(1, 0);
map<LL, bool> mp;
for (int i = 1; i < now.size(); i++) {
if (mp[now[i]]) continue;
vector<LL>().swap(tmp); mp[now[i]] = true;
for (int j = 0; j < now.size(); j++) {
if (j == 0) tmp.push_back(now[j] * (lev - 2));
else if (j != i) tmp.push_back(now[j] * (lev - 1));
}
mn = min(mn, dfs(tmp, lev - 1, pro * Frac(1, mxp.size())));
}
res += mn;
}
if (mxp.size() > (mxp[0] == 0)) {
vector<LL> tmp; Frac mn(1, 0); map<LL, bool> mp2;
for (int i = mxp[(mxp[0] == 0)], j = 1; j < now.size(); j++) {
if (i == j || mp2[now[j]]) continue;
mp2[now[j]] = true;
vector<LL>().swap(tmp);
for (int k = 0; k < now.size(); k++) {
if (k == i) tmp.push_back(now[k] * (lev - 2));
else if (k != j) tmp.push_back(now[k] * (lev - 1));
}
mn = min(mn, dfs(tmp, lev - 1, pro * Frac(1, mxp.size())));
}
res += mn * Frac((mxp.size() - (mxp[0] == 0)), 1);
}
// if (lev >= 7) printf("%d %.6lf %.6lf\n", lev, pro.val(), res.val());
// if (lev >= 7) { for (int i : now) cout << i << " "; cout << endl; }
return res;
}
LL a, b;
void exgcd(LL x, LL y) {
if (x == 1) { a = 1, b = 0; return; }
exgcd(y % x, x);
LL d = y / x, tmp = a;
a = b - tmp * d, b = tmp;
}
LL solve() {
LL now = 1, res = 0;
for (int i = 1; i <= T; i++) {
LL res1 = (num[i][0] - res), g = __gcd(now, num[i][1]);
if (res1 < 0) swap(num[i][0], res), swap(num[i][1], now), res1 = -res1;
if (res1 % g != 0) { printf("error\n"); exit(0); }
LL res2 = res1 / g;
a = 0, b = 0; exgcd(now / g, num[i][1] / g);
// cout << a << " " << b << endl;
LL pos = (a % (num[i][1] / g) * res2 % (num[i][1] / g) + num[i][1] / g) % (num[i][1] / g);
res = res + pos * now;
// write(res, '\n');
now = now / g * num[i][1];
}
return res;
}
int main() {
// freopen("ex_data2.in", "r", stdin);
scanf("%d", &T);
for (int i = 1; i <= T; i++) {
scanf("%lld %lld", &num[i][0], &num[i][1]);
}
n = solve();
// cout << n << endl;
if (n < 2) return printf("error\n"), 0;
// if (n >= 12) return printf("0.000000\n"), 0;//, (Frac(1, n - 2) + Frac(1, n)).val()), 0;
vector<LL> tmp;
for (int i = 1; i <= n; i++) tmp.push_back(1);
printf("%.6lf", dfs(tmp, n, Frac(1, 1)).val());
}
詳細信息
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 0ms
memory: 3980kb
input:
1 2 3
output:
0.500000
result:
ok single line: '0.500000'
Test #2:
score: 5
Accepted
time: 0ms
memory: 3984kb
input:
1 3 5
output:
0.666667
result:
ok single line: '0.666667'
Test #3:
score: 5
Accepted
time: 0ms
memory: 4124kb
input:
1 4 5
output:
0.625000
result:
ok single line: '0.625000'
Test #4:
score: 5
Accepted
time: 0ms
memory: 3752kb
input:
1 0 4
output:
error
result:
ok single line: 'error'
Test #5:
score: 5
Accepted
time: 0ms
memory: 3792kb
input:
1 1 3
output:
error
result:
ok single line: 'error'
Subtask #2:
score: 10
Accepted
Test #6:
score: 10
Accepted
time: 0ms
memory: 3756kb
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: 10
Accepted
time: 0ms
memory: 3828kb
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: 10
Accepted
time: 0ms
memory: 3840kb
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: 10
Accepted
time: 0ms
memory: 4088kb
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: 10
Accepted
time: 0ms
memory: 3824kb
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: 10
Accepted
time: 0ms
memory: 4080kb
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: 10
Accepted
time: 0ms
memory: 3824kb
input:
2 1000000007 1000000008 2 4
output:
error
result:
ok single line: 'error'
Test #13:
score: 10
Accepted
time: 0ms
memory: 3716kb
input:
3 0 1001 0 241221531 0 2
output:
error
result:
ok single line: 'error'
Test #14:
score: 10
Accepted
time: 0ms
memory: 4112kb
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: 3700kb
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: 10
Accepted
time: 0ms
memory: 3840kb
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: 10
Accepted
time: 0ms
memory: 3828kb
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: 10
Accepted
time: 0ms
memory: 4112kb
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: 10
Accepted
time: 0ms
memory: 3980kb
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: 10
Accepted
time: 0ms
memory: 3920kb
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: 10
Accepted
time: 0ms
memory: 3816kb
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: 10
Accepted
time: 0ms
memory: 3988kb
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: 10
Accepted
time: 0ms
memory: 4064kb
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: 10
Accepted
time: 0ms
memory: 3792kb
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: 10
Accepted
time: 0ms
memory: 3756kb
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: 10
Accepted
time: 0ms
memory: 3728kb
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: 0ms
memory: 3792kb
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: 10
Accepted
time: 0ms
memory: 3880kb
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: 10
Accepted
time: 0ms
memory: 3764kb
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: 10
Accepted
time: 0ms
memory: 3836kb
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: 10
Accepted
time: 0ms
memory: 3920kb
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: 10
Accepted
time: 0ms
memory: 3984kb
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: 10
Accepted
time: 0ms
memory: 3900kb
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: 10
Accepted
time: 0ms
memory: 3884kb
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: 10
Accepted
time: 0ms
memory: 3900kb
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: 10
Accepted
time: 0ms
memory: 3988kb
input:
1 5 6
output:
0.466667
result:
ok single line: '0.466667'
Test #37:
score: 10
Accepted
time: 0ms
memory: 3944kb
input:
1 6 7
output:
0.416667
result:
ok single line: '0.416667'
Test #38:
score: 10
Accepted
time: 0ms
memory: 3884kb
input:
1 7 8
output:
0.342857
result:
ok single line: '0.342857'
Test #39:
score: 10
Accepted
time: 0ms
memory: 4116kb
input:
4 0 2 0 4 2 3 3 5
output:
0.291667
result:
ok single line: '0.291667'
Test #40:
score: 10
Accepted
time: 1ms
memory: 3900kb
input:
4 0 3 0 9 1 2 4 5
output:
0.253968
result:
ok single line: '0.253968'
Test #41:
score: 10
Accepted
time: 1ms
memory: 4124kb
input:
3 0 2 0 5 1 3
output:
0.225000
result:
ok single line: '0.225000'
Test #42:
score: 10
Accepted
time: 0ms
memory: 3764kb
input:
6 0 1 0 2 0 6 0 12 0 4 0 3
output:
error
result:
ok single line: 'error'
Test #43:
score: 10
Accepted
time: 0ms
memory: 3760kb
input:
6 837250 1574381 22682 54289 20 29 81 233 6139 6757 0 1
output:
error
result:
ok single line: 'error'
Test #44:
score: 10
Accepted
time: 0ms
memory: 3760kb
input:
6 12521 54289 1478324 1574381 20 29 171 233 0 1 5298 6757
output:
error
result:
ok single line: 'error'
Test #45:
score: 10
Accepted
time: 0ms
memory: 3756kb
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: 10
Accepted
time: 0ms
memory: 3896kb
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
Runtime Error
Dependency #1:
100%
Accepted
Dependency #4:
100%
Accepted
Test #47:
score: 5
Accepted
time: 4ms
memory: 4616kb
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
Accepted
time: 5ms
memory: 4612kb
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: 5
Accepted
time: 5ms
memory: 5284kb
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: 5
Accepted
time: 9ms
memory: 5324kb
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
Runtime Error
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
Time Limit Exceeded
Test #57:
score: 0
Time Limit Exceeded
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:
result:
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
0%