QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#789693 | #5444. Tavern Chess | HQLF | AC ✓ | 1633ms | 403552kb | C++20 | 4.6kb | 2024-11-27 21:28:38 | 2024-11-27 21:28:44 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ldb=long double;
using ull=unsigned long long;
const long long inf=0x3f3f3f3f3f3f3f3f;
using i128=__int128;
const int mod=1000000007;
const long double eps=0.00000000001;
struct frac
{
ll fz;
ll fm;
frac operator+(const frac&x)const
{
ll lcm=(fm*x.fm)/gcd(fm,x.fm);
ll fz1=fz*(lcm)/fm;
ll fz2=x.fz*(lcm)/x.fm;
ll tfz=fz1+fz2;
ll g=gcd(tfz,lcm);
frac ans={tfz/g,lcm/g};
return ans;
}
frac operator*(const frac&x)const
{
ll tfm=fm*x.fm;
ll tfz=fz*x.fz;
ll g=gcd(tfz,tfm);
frac ans={tfz/g,tfm/g};
return ans;
}
};
struct mn
{
ll atk;
ll hp;
ll num;
};
struct zt
{
vector<mn>a;
vector<mn>b;
};
struct node
{
zt z;
ll f;
ldb p;
};
void solve()
{
ll n,m;
cin>>n>>m;
zt z;
for(ll i=1;i<=n;i++)
{
ll x;
cin>>x;
z.a.push_back({x,x,0});
}
for(ll i=1;i<=m;i++)
{
ll x;
cin>>x;
z.b.push_back({x,x,0});
}
queue<node>q;
if(z.a.size()==z.b.size())
{
q.push({z,0,0.5});
q.push({z,1,0.5});
}
else if(z.a.size()>z.b.size())
{
q.push({z,0,1});
}
else if(z.a.size()<z.b.size())
{
q.push({z,1,1});
}
ldb a=0;
ldb b=0;
ldb d=0;
while(!q.empty())
{
node k=q.front();
q.pop();
if(k.f==0)
{
ll la=(ll)k.z.a.size();
ll wz=0;
ll num=k.z.a[0].num;
for(ll i=0;i<=la-1;i++)
{
if(k.z.a[i].num<num)
{
num=k.z.a[i].num;
wz=i;
}
}
ll lb=(ll)k.z.b.size();
for(ll i=0;i<=lb-1;i++)
{
node tk=k;
tk.z.a[wz].hp-=tk.z.b[i].atk;
tk.z.a[wz].num++;
tk.z.b[i].hp-=tk.z.a[wz].atk;
if(tk.z.a[wz].hp<=0)
{
tk.z.a.erase(tk.z.a.begin()+wz);
}
if(tk.z.b[i].hp<=0)
{
tk.z.b.erase(tk.z.b.begin()+i);
}
tk.p=tk.p*(1.0/ldb(lb));
tk.f^=1;
if(tk.z.a.empty()&&tk.z.b.empty())
{
d=d+tk.p;
}
else if(!tk.z.a.empty()&&tk.z.b.empty())
{
a=a+tk.p;
}
else if(tk.z.a.empty()&&!tk.z.b.empty())
{
b=b+tk.p;
}
else
{
q.push(tk);
}
}
}
else if(k.f==1)
{
ll lb=(ll)k.z.b.size();
ll wz=0;
ll num=k.z.b[0].num;
for(ll i=0;i<=lb-1;i++)
{
if(k.z.b[i].num<num)
{
num=k.z.b[i].num;
wz=i;
}
}
ll la=(ll)k.z.a.size();
for(ll i=0;i<=la-1;i++)
{
node tk=k;
tk.z.a[i].hp-=tk.z.b[wz].atk;
tk.z.b[wz].hp-=tk.z.a[i].atk;
tk.z.b[wz].num++;
if(tk.z.a[i].hp<=0)
{
tk.z.a.erase(tk.z.a.begin()+i);
}
if(tk.z.b[wz].hp<=0)
{
tk.z.b.erase(tk.z.b.begin()+wz);
}
tk.p=tk.p*(1.0/ldb(la));
tk.f^=1;
if(tk.z.a.empty()&&tk.z.b.empty())
{
d=d+tk.p;
}
else if(!tk.z.a.empty()&&tk.z.b.empty())
{
a=a+tk.p;
}
else if(tk.z.a.empty()&&!tk.z.b.empty())
{
b=b+tk.p;
}
else
{
q.push(tk);
}
}
}
}
printf("%.20Lf\n",a);
printf("%.20Lf\n",b);
printf("%.20Lf\n",d);
}
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
ll _=1;
// cin>>_;
while(_--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3920kb
input:
2 3 2 5 3 4 1
output:
0.12500000000000000000 0.75000000000000000000 0.12500000000000000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 7ms
memory: 6088kb
input:
6 6 1 1 4 5 1 4 1 1 4 5 1 4
output:
0.24186728395061729084 0.24186728395061729082 0.51626543209876544680
result:
ok 3 numbers
Test #3:
score: 0
Accepted
time: 4ms
memory: 5080kb
input:
7 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1
output:
0.00000000000000000000 0.00000000000000000000 1.00000000000000013574
result:
ok 3 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
1 7 7 1 1 1 1 1 1 1
output:
0.00000000000000000000 0.00000000000000000000 0.99999999999999999962
result:
ok 3 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
2 3 736618938 652769331 328875880 97571721 44608905
output:
1.00000000000000000000 0.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #6:
score: 0
Accepted
time: 1ms
memory: 4052kb
input:
5 4 53585130 731696211 668322278 611205195 158818781 569587984 776042583 745745433 330119007
output:
0.06684027777777777777 0.66435185185185184978 0.26880787037037037036
result:
ok 3 numbers
Test #7:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
7 2 578505806 551611151 92903265 403642038 542119417 57334031 307573613 897644535 168524310
output:
0.99999999999999999973 0.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #8:
score: 0
Accepted
time: 4ms
memory: 5220kb
input:
5 6 113196606 64768263 772808463 787707989 500151952 481840741 676847825 4641268 431386165 847736311 169677832
output:
0.13632317386831275788 0.52239718364197530704 0.34127964248971193683
result:
ok 3 numbers
Test #9:
score: 0
Accepted
time: 19ms
memory: 10520kb
input:
6 6 260666773 527612597 471926610 702232282 559007797 606173983 560573055 928117268 101411867 875949818 907478252 182117037
output:
0.00000000000000000000 0.96081957304526783794 0.03918042695473251053
result:
ok 3 numbers
Test #10:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
3 3 333377599 3066695 67916629 426841530 865184552 974638244
output:
0.00000000000000000000 1.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #11:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
1 1 529429019 529428649
output:
1.00000000000000000000 0.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #12:
score: 0
Accepted
time: 0ms
memory: 4088kb
input:
3 3 12886596 817437415 465037461 12886473 817437448 465037967
output:
0.06944444444444444445 0.65277777777777777775 0.27777777777777777778
result:
ok 3 numbers
Test #13:
score: 0
Accepted
time: 26ms
memory: 14204kb
input:
6 6 211213374 319527017 257080158 176742665 53109345 33822515 53109265 319527076 176743175 257080012 211212799 33822353
output:
0.42339995927640611565 0.31938658479080934236 0.25721345593278465100
result:
ok 3 numbers
Test #14:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
1 2 1 1 1
output:
0.00000000000000000000 1.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #15:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
1 2 1 1 3
output:
0.00000000000000000000 1.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #16:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
1 2 2 4 2
output:
0.00000000000000000000 1.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #17:
score: 0
Accepted
time: 0ms
memory: 3984kb
input:
1 2 3 5 5
output:
0.00000000000000000000 1.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #18:
score: 0
Accepted
time: 0ms
memory: 3948kb
input:
1 2 4 1 2
output:
1.00000000000000000000 0.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #19:
score: 0
Accepted
time: 0ms
memory: 4076kb
input:
1 2 5 2 5
output:
0.00000000000000000000 0.00000000000000000000 1.00000000000000000000
result:
ok 3 numbers
Test #20:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
1 2 5 5 5
output:
0.00000000000000000000 1.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #21:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
2 2 1 1 1 3
output:
0.00000000000000000000 1.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #22:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
2 2 1 1 2 3
output:
0.00000000000000000000 1.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #23:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
2 2 1 4 2 5
output:
0.00000000000000000000 0.50000000000000000000 0.50000000000000000000
result:
ok 3 numbers
Test #24:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
2 2 2 2 1 4
output:
0.00000000000000000000 0.00000000000000000000 1.00000000000000000000
result:
ok 3 numbers
Test #25:
score: 0
Accepted
time: 0ms
memory: 4020kb
input:
2 2 3 2 4 1
output:
0.00000000000000000000 0.50000000000000000000 0.50000000000000000000
result:
ok 3 numbers
Test #26:
score: 0
Accepted
time: 0ms
memory: 4076kb
input:
2 2 3 3 1 3
output:
1.00000000000000000000 0.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #27:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
2 2 3 3 2 4
output:
0.00000000000000000000 0.00000000000000000000 1.00000000000000000000
result:
ok 3 numbers
Test #28:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
2 2 3 3 5 3
output:
0.00000000000000000000 1.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #29:
score: 0
Accepted
time: 0ms
memory: 3980kb
input:
2 2 4 3 2 1
output:
1.00000000000000000000 0.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #30:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
2 2 4 3 4 4
output:
0.00000000000000000000 1.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #31:
score: 0
Accepted
time: 0ms
memory: 4028kb
input:
2 2 5 1 5 2
output:
0.12500000000000000000 0.62500000000000000000 0.25000000000000000000
result:
ok 3 numbers
Test #32:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
2 2 5 1 5 3
output:
0.12500000000000000000 0.62500000000000000000 0.25000000000000000000
result:
ok 3 numbers
Test #33:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
2 2 5 2 2 3
output:
0.87500000000000000000 0.00000000000000000000 0.12500000000000000000
result:
ok 3 numbers
Test #34:
score: 0
Accepted
time: 0ms
memory: 3984kb
input:
2 2 5 4 1 2
output:
1.00000000000000000000 0.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #35:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
2 2 5 4 3 5
output:
0.87500000000000000000 0.00000000000000000000 0.12500000000000000000
result:
ok 3 numbers
Test #36:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
2 2 5 5 1 4
output:
1.00000000000000000000 0.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #37:
score: 0
Accepted
time: 0ms
memory: 4016kb
input:
2 2 5 5 2 2
output:
1.00000000000000000000 0.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #38:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
1 1 6 6
output:
0.00000000000000000000 0.00000000000000000000 1.00000000000000000000
result:
ok 3 numbers
Test #39:
score: 0
Accepted
time: 1ms
memory: 3940kb
input:
5 5 6 5 9 9 3 3 5 9 9 6
output:
0.29787037037037037142 0.27877314814814814863 0.42335648148148148230
result:
ok 3 numbers
Test #40:
score: 0
Accepted
time: 16ms
memory: 9552kb
input:
6 6 10 2 3 4 5 7 5 2 4 3 10 7
output:
0.25401045685442389521 0.19277370541838136046 0.55321583772719474224
result:
ok 3 numbers
Test #41:
score: 0
Accepted
time: 173ms
memory: 54628kb
input:
7 7 7 6 8 6 7 3 9 7 6 9 8 7 3 6
output:
0.31091375142566929701 0.36576836791401948093 0.32331788066031086356
result:
ok 3 numbers
Test #42:
score: 0
Accepted
time: 5ms
memory: 7176kb
input:
6 6 5 4 7 9 9 10 9 4 9 7 5 10
output:
0.21694243505658436958 0.32785654578189299995 0.45520101916152263754
result:
ok 3 numbers
Test #43:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
4 4 9 7 10 6 9 7 6 10
output:
0.33087384259259259260 0.26229745370370370364 0.40682870370370370351
result:
ok 3 numbers
Test #44:
score: 0
Accepted
time: 0ms
memory: 4088kb
input:
3 3 3 10 3 3 10 3
output:
0.18750000000000000000 0.18750000000000000000 0.62499999999999999995
result:
ok 3 numbers
Test #45:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
2 2 3 4 3 4
output:
0.00000000000000000000 0.00000000000000000000 1.00000000000000000000
result:
ok 3 numbers
Test #46:
score: 0
Accepted
time: 372ms
memory: 124512kb
input:
7 7 922750124 99645786 685060385 948410807 266950246 996521461 883971852 266950246 99645786 883971852 685060385 922750124 996521461 948410807
output:
0.36335637141623607570 0.27956640551185747766 0.35707722307190632984
result:
ok 3 numbers
Test #47:
score: 0
Accepted
time: 502ms
memory: 145312kb
input:
7 7 241155912 361580213 393947982 781406405 485516551 277202028 115028196 485516551 361580213 115028196 393947982 241155912 277202028 781406405
output:
0.37017609359987174584 0.27878994530356416401 0.35103396109656366975
result:
ok 3 numbers
Test #48:
score: 0
Accepted
time: 250ms
memory: 79232kb
input:
7 7 565748008 734938287 873800405 879803305 473331973 893190834 623040014 473331973 734938287 623040014 873800405 565748008 893190834 879803305
output:
0.36430590801663661392 0.31560355422711797489 0.32009053775624567167
result:
ok 3 numbers
Test #49:
score: 0
Accepted
time: 894ms
memory: 224280kb
input:
7 7 14 4 6 5 201506030 15 15 4 14 201506030 15 15 6 5
output:
0.17818379165237725436 0.33708150986989414939 0.48473469847772628221
result:
ok 3 numbers
Test #50:
score: 0
Accepted
time: 477ms
memory: 113396kb
input:
7 7 3 2 3 5 784861968 2 1 2 3 784861968 1 2 3 5
output:
0.22307502187328729363 0.31615158023316148917 0.46077339789355058997
result:
ok 3 numbers
Test #51:
score: 0
Accepted
time: 1324ms
memory: 310628kb
input:
7 7 8 15 3 9 168061718 2 5 15 8 168061718 5 2 3 9
output:
0.21296959598805238654 0.31996299506721363528 0.46706740894473277429
result:
ok 3 numbers
Test #52:
score: 0
Accepted
time: 448ms
memory: 115920kb
input:
7 7 859736717 19 19 18 13 10 7 7 10 13 18 19 19 859736717
output:
0.39362065259521391544 0.14796726625160088747 0.45841208115318509016
result:
ok 3 numbers
Test #53:
score: 0
Accepted
time: 607ms
memory: 156324kb
input:
7 7 761045932 18 13 11 9 7 6 6 7 9 11 13 18 761045932
output:
0.38246768955516716765 0.14749323865472663147 0.47003907179010616445
result:
ok 3 numbers
Test #54:
score: 0
Accepted
time: 692ms
memory: 183976kb
input:
7 7 379524878 17 16 14 10 6 1 1 6 10 14 16 17 379524878
output:
0.37926029329990412428 0.17653672207984268293 0.44420298462025280725
result:
ok 3 numbers
Test #55:
score: 0
Accepted
time: 833ms
memory: 214144kb
input:
7 7 986258805 329018732 16 14 10 10 4 4 10 10 14 16 329018732 986258805
output:
0.33520652350806679769 0.16822818648180073076 0.49656529001013077594
result:
ok 3 numbers
Test #56:
score: 0
Accepted
time: 815ms
memory: 208224kb
input:
7 7 402437510 39859989 20 20 18 17 7 7 17 18 20 20 39859989 402437510
output:
0.32869947364315120478 0.16026305826870608550 0.51103746808814087252
result:
ok 3 numbers
Test #57:
score: 0
Accepted
time: 999ms
memory: 253404kb
input:
7 7 719895666 88341845 15 11 10 6 5 5 6 10 11 15 88341845 719895666
output:
0.34154105876287181245 0.16943659666569724757 0.48902234457142882305
result:
ok 3 numbers
Test #58:
score: 0
Accepted
time: 1350ms
memory: 325580kb
input:
7 7 22 657372492 8 20 531193761 10 21 8 22 20 657372492 531193761 21 10
output:
0.28303203585850862325 0.21433164140271826547 0.50263632273877404809
result:
ok 3 numbers
Test #59:
score: 0
Accepted
time: 1633ms
memory: 403552kb
input:
7 7 8 559730577 2 23 543514141 3 24 2 8 23 559730577 543514141 24 3
output:
0.28368161658342608611 0.22201571344977773303 0.49430266996679831268
result:
ok 3 numbers
Test #60:
score: 0
Accepted
time: 1023ms
memory: 244576kb
input:
7 7 24 416408320 4 25 698151361 24 15 4 24 25 416408320 698151361 15 24
output:
0.29751636844278468347 0.24728658696748365762 0.45519704458973258535
result:
ok 3 numbers