QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#73931 | #5444. Tavern Chess | nweeks | ML | 574ms | 107736kb | C++17 | 4.8kb | 2023-01-29 16:44:57 | 2023-01-29 16:44:59 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
bool first = true;
string res = "[";
for (const auto &x : v) {
if (!first)
res += ", ";
first = false;
res += to_string(x);
}
res += "]";
return res;
}
void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
cout << ' ' << to_string(H);
dbg_out(T...);
}
#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
const int MAXN = 7;
int alice[MAXN], bob[MAXN];
int cntL, cntR;
map<tuple<vector<int>, vector<int>, vector<int>, vector<int>, int>,
tuple<double, double, double>>
cache;
tuple<double, double, double> solve(vector<int> killedA, vector<int> killedB,
int side, vector<int> freqA,
vector<int> freqB) {
if (cache.count({killedA, killedB, freqA, freqB, side}))
return cache[{killedA, killedB, freqA, freqB, side}];
int aliveA = 0, aliveB = 0;
for (int x : killedA)
if (x == -1)
aliveA++;
for (int x : killedB)
if (x == -1)
aliveB++;
double probA = 0, probDraw = 0, probB = 0;
if (aliveA == 0 and aliveB == 0) {
probDraw = 1;
return cache[{killedA, killedB, freqA, freqB, side}] =
tuple(probA, probDraw, probB);
} else if (aliveA == 0) {
probB = 1;
return cache[{killedA, killedB, freqA, freqB, side}] =
tuple(probA, probDraw, probB);
} else if (aliveB == 0) {
probA = 1;
return cache[{killedA, killedB, freqA, freqB, side}] =
tuple(probA, probDraw, probB);
}
vector<int> hpAlice(cntL), hpBob(cntR);
for (int i = 0; i < cntL; ++i)
hpAlice[i] = alice[i];
for (int i = 0; i < cntR; ++i)
hpBob[i] = bob[i];
for (int i = 0; i < cntL; ++i)
if (killedA[i] >= 0)
hpBob[killedA[i]] -= alice[i];
for (int i = 0; i < cntR; ++i)
if (killedB[i] >= 0)
hpAlice[killedB[i]] -= bob[i];
auto playAlice = [&]() {
int pos = 0;
while (killedA[pos] != -1)
++pos;
for (int i = pos + 1; i < cntL; ++i)
if (killedA[i] == -1 and freqA[i] < freqA[pos])
pos = i;
double a = 0, d = 0, b = 0;
for (int i = 0; i < cntR; ++i)
if (killedB[i] == -1) {
if (alice[pos] >= hpBob[i])
killedB[i] = pos;
if (bob[i] >= hpAlice[pos])
killedA[pos] = i;
freqA[pos]++;
auto [aa, dd, bb] = solve(killedA, killedB, 1, freqA, freqB);
freqA[pos]--;
killedA[pos] = -1;
killedB[i] = -1;
a += aa / aliveB, d += dd / aliveB, b += bb / aliveB;
}
return tuple(a, d, b);
};
auto playBob = [&]() {
int pos = 0;
while (killedB[pos] != -1)
++pos;
for (int i = pos + 1; i < cntR; ++i)
if (killedB[i] == -1 and freqB[i] < freqB[pos])
pos = i;
double a = 0, d = 0, b = 0;
for (int i = 0; i < cntL; ++i)
if (killedA[i] == -1) {
if (alice[i] >= hpBob[pos])
killedB[pos] = i;
if (bob[pos] >= hpAlice[i])
killedA[i] = pos;
freqB[pos]++;
auto [aa, dd, bb] = solve(killedA, killedB, -1, freqA, freqB);
freqB[pos]--;
killedA[i] = -1;
killedB[pos] = -1;
a += aa / aliveA, d += dd / aliveA, b += bb / aliveA;
}
return tuple(a, d, b);
};
if (side == 0) {
if (aliveA > aliveB) {
auto [a, d, b] = playAlice();
probA = a, probDraw = d, probB = b;
} else if (aliveA < aliveB) {
auto [a, d, b] = playBob();
probA = a, probDraw = d, probB = b;
} else {
auto [a, d, b] = playAlice();
probA = a, probDraw = d, probB = b;
tie(a, d, b) = playBob();
probA += a, probDraw += d, probB += b;
probA /= 2, probDraw /= 2, probB /= 2;
}
} else if (side == -1) {
auto [a, d, b] = playAlice();
probA = a, probDraw = d, probB = b;
} else if (side == 1) {
auto [a, d, b] = playBob();
probA = a, probDraw = d, probB = b;
}
dbg(aliveA, aliveB, side);
dbg(killedA, killedB, probA, probDraw, probB);
return cache[{killedA, killedB, freqA, freqB, side}] =
tuple(probA, probDraw, probB);
}
signed main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> cntL >> cntR;
for (int i = 0; i < cntL; ++i)
cin >> alice[i];
for (int i = 0; i < cntR; ++i)
cin >> bob[i];
vector<int> killedA(cntL, -1), killedB(cntR, -1);
vector<int> freqA(cntL, 0), freqB(cntR, 0);
auto [a, d, b] = solve(killedA, killedB, 0, freqA, freqB);
cout << setprecision(15) << fixed << a << ' ' << b << ' ' << d << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3600kb
input:
2 3 2 5 3 4 1
output:
0.125000000000000 0.750000000000000 0.125000000000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 82ms
memory: 25660kb
input:
6 6 1 1 4 5 1 4 1 1 4 5 1 4
output:
0.241867283950617 0.241867283950617 0.516265432098765
result:
ok 3 numbers
Test #3:
score: 0
Accepted
time: 34ms
memory: 15304kb
input:
7 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1
output:
0.000000000000000 0.000000000000000 1.000000000000000
result:
ok 3 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
1 7 7 1 1 1 1 1 1 1
output:
0.000000000000000 0.000000000000000 1.000000000000000
result:
ok 3 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
2 3 736618938 652769331 328875880 97571721 44608905
output:
1.000000000000000 0.000000000000000 0.000000000000000
result:
ok 3 numbers
Test #6:
score: 0
Accepted
time: 3ms
memory: 4056kb
input:
5 4 53585130 731696211 668322278 611205195 158818781 569587984 776042583 745745433 330119007
output:
0.066840277777778 0.664351851851852 0.268807870370370
result:
ok 3 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
7 2 578505806 551611151 92903265 403642038 542119417 57334031 307573613 897644535 168524310
output:
1.000000000000000 0.000000000000000 0.000000000000000
result:
ok 3 numbers
Test #8:
score: 0
Accepted
time: 34ms
memory: 15944kb
input:
5 6 113196606 64768263 772808463 787707989 500151952 481840741 676847825 4641268 431386165 847736311 169677832
output:
0.136323173868313 0.522397183641975 0.341279642489712
result:
ok 3 numbers
Test #9:
score: 0
Accepted
time: 304ms
memory: 71920kb
input:
6 6 260666773 527612597 471926610 702232282 559007797 606173983 560573055 928117268 101411867 875949818 907478252 182117037
output:
0.000000000000000 0.960819573045267 0.039180426954733
result:
ok 3 numbers
Test #10:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
3 3 333377599 3066695 67916629 426841530 865184552 974638244
output:
0.000000000000000 1.000000000000000 0.000000000000000
result:
ok 3 numbers
Test #11:
score: 0
Accepted
time: 2ms
memory: 3748kb
input:
1 1 529429019 529428649
output:
1.000000000000000 0.000000000000000 0.000000000000000
result:
ok 3 numbers
Test #12:
score: 0
Accepted
time: 2ms
memory: 3648kb
input:
3 3 12886596 817437415 465037461 12886473 817437448 465037967
output:
0.069444444444444 0.652777777777778 0.277777777777778
result:
ok 3 numbers
Test #13:
score: 0
Accepted
time: 574ms
memory: 107736kb
input:
6 6 211213374 319527017 257080158 176742665 53109345 33822515 53109265 319527076 176743175 257080012 211212799 33822353
output:
0.423399959276406 0.319386584790809 0.257213455932785
result:
ok 3 numbers
Test #14:
score: 0
Accepted
time: 2ms
memory: 3596kb
input:
1 2 1 1 1
output:
0.000000000000000 1.000000000000000 0.000000000000000
result:
ok 3 numbers
Test #15:
score: 0
Accepted
time: 2ms
memory: 3748kb
input:
1 2 1 1 3
output:
0.000000000000000 1.000000000000000 0.000000000000000
result:
ok 3 numbers
Test #16:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
1 2 2 4 2
output:
0.000000000000000 1.000000000000000 0.000000000000000
result:
ok 3 numbers
Test #17:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
1 2 3 5 5
output:
0.000000000000000 1.000000000000000 0.000000000000000
result:
ok 3 numbers
Test #18:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
1 2 4 1 2
output:
1.000000000000000 0.000000000000000 0.000000000000000
result:
ok 3 numbers
Test #19:
score: 0
Accepted
time: 2ms
memory: 3676kb
input:
1 2 5 2 5
output:
0.000000000000000 0.000000000000000 1.000000000000000
result:
ok 3 numbers
Test #20:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
1 2 5 5 5
output:
0.000000000000000 1.000000000000000 0.000000000000000
result:
ok 3 numbers
Test #21:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
2 2 1 1 1 3
output:
0.000000000000000 1.000000000000000 0.000000000000000
result:
ok 3 numbers
Test #22:
score: 0
Accepted
time: 2ms
memory: 3672kb
input:
2 2 1 1 2 3
output:
0.000000000000000 1.000000000000000 0.000000000000000
result:
ok 3 numbers
Test #23:
score: 0
Accepted
time: 2ms
memory: 3600kb
input:
2 2 1 4 2 5
output:
0.000000000000000 0.500000000000000 0.500000000000000
result:
ok 3 numbers
Test #24:
score: 0
Accepted
time: 2ms
memory: 3680kb
input:
2 2 2 2 1 4
output:
0.000000000000000 0.000000000000000 1.000000000000000
result:
ok 3 numbers
Test #25:
score: 0
Accepted
time: 2ms
memory: 3764kb
input:
2 2 3 2 4 1
output:
0.000000000000000 0.500000000000000 0.500000000000000
result:
ok 3 numbers
Test #26:
score: 0
Accepted
time: 2ms
memory: 3752kb
input:
2 2 3 3 1 3
output:
1.000000000000000 0.000000000000000 0.000000000000000
result:
ok 3 numbers
Test #27:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
2 2 3 3 2 4
output:
0.000000000000000 0.000000000000000 1.000000000000000
result:
ok 3 numbers
Test #28:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
2 2 3 3 5 3
output:
0.000000000000000 1.000000000000000 0.000000000000000
result:
ok 3 numbers
Test #29:
score: 0
Accepted
time: 2ms
memory: 3552kb
input:
2 2 4 3 2 1
output:
1.000000000000000 0.000000000000000 0.000000000000000
result:
ok 3 numbers
Test #30:
score: 0
Accepted
time: 2ms
memory: 3744kb
input:
2 2 4 3 4 4
output:
0.000000000000000 1.000000000000000 0.000000000000000
result:
ok 3 numbers
Test #31:
score: 0
Accepted
time: 2ms
memory: 3744kb
input:
2 2 5 1 5 2
output:
0.125000000000000 0.625000000000000 0.250000000000000
result:
ok 3 numbers
Test #32:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
2 2 5 1 5 3
output:
0.125000000000000 0.625000000000000 0.250000000000000
result:
ok 3 numbers
Test #33:
score: 0
Accepted
time: 2ms
memory: 3744kb
input:
2 2 5 2 2 3
output:
0.875000000000000 0.000000000000000 0.125000000000000
result:
ok 3 numbers
Test #34:
score: 0
Accepted
time: 2ms
memory: 3584kb
input:
2 2 5 4 1 2
output:
1.000000000000000 0.000000000000000 0.000000000000000
result:
ok 3 numbers
Test #35:
score: 0
Accepted
time: 2ms
memory: 3640kb
input:
2 2 5 4 3 5
output:
0.875000000000000 0.000000000000000 0.125000000000000
result:
ok 3 numbers
Test #36:
score: 0
Accepted
time: 2ms
memory: 3752kb
input:
2 2 5 5 1 4
output:
1.000000000000000 0.000000000000000 0.000000000000000
result:
ok 3 numbers
Test #37:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
2 2 5 5 2 2
output:
1.000000000000000 0.000000000000000 0.000000000000000
result:
ok 3 numbers
Test #38:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
1 1 6 6
output:
0.000000000000000 0.000000000000000 1.000000000000000
result:
ok 3 numbers
Test #39:
score: 0
Accepted
time: 3ms
memory: 5504kb
input:
5 5 6 5 9 9 3 3 5 9 9 6
output:
0.297870370370370 0.278773148148148 0.423356481481482
result:
ok 3 numbers
Test #40:
score: 0
Accepted
time: 286ms
memory: 66160kb
input:
6 6 10 2 3 4 5 7 5 2 4 3 10 7
output:
0.254010456854424 0.192773705418381 0.553215837727195
result:
ok 3 numbers
Test #41:
score: -100
Memory Limit Exceeded
input:
7 7 7 6 8 6 7 3 9 7 6 9 8 7 3 6