QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#789645 | #5444. Tavern Chess | HQLF | WA | 256ms | 51788kb | C++20 | 4.8kb | 2024-11-27 21:18:18 | 2024-11-27 21:18:21 |
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;
frac 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,{1,2}});
q.push({z,1,{1,2}});
}
else if(z.a.size()>z.b.size())
{
q.push({z,0,{1,1}});
}
else if(z.a.size()<z.b.size())
{
q.push({z,1,{1,1}});
}
frac a={0,1};
frac b={0,1};
frac d={0,1};
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);
}
frac t;
t.fz=1;
t.fm=lb;
tk.p=tk.p*t;
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);
}
frac t;
t.fz=1;
t.fm=la;
tk.p=tk.p*t;
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);
}
}
}
}
ldb sa=ldb(a.fz)/ldb(a.fm);
ldb sb=ldb(b.fz)/ldb(b.fm);
ldb sd=ldb(d.fz)/ldb(d.fm);
printf("%.20Lf\n",sa);
printf("%.20Lf\n",sb);
printf("%.20Lf\n",sd);
}
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: 1ms
memory: 3720kb
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: 9ms
memory: 6028kb
input:
6 6 1 1 4 5 1 4 1 1 4 5 1 4
output:
0.24186728395061728395 0.24186728395061728395 0.51626543209876543211
result:
ok 3 numbers
Test #3:
score: 0
Accepted
time: 5ms
memory: 5236kb
input:
7 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1
output:
0.00000000000000000000 0.00000000000000000000 1.00000000000000000000
result:
ok 3 numbers
Test #4:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
1 7 7 1 1 1 1 1 1 1
output:
0.00000000000000000000 0.00000000000000000000 1.00000000000000000000
result:
ok 3 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3848kb
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: 3744kb
input:
5 4 53585130 731696211 668322278 611205195 158818781 569587984 776042583 745745433 330119007
output:
0.06684027777777777778 0.66435185185185185184 0.26880787037037037038
result:
ok 3 numbers
Test #7:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
7 2 578505806 551611151 92903265 403642038 542119417 57334031 307573613 897644535 168524310
output:
1.00000000000000000000 0.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #8:
score: 0
Accepted
time: 6ms
memory: 5016kb
input:
5 6 113196606 64768263 772808463 787707989 500151952 481840741 676847825 4641268 431386165 847736311 169677832
output:
0.13632317386831275720 0.52239718364197530867 0.34127964248971193414
result:
ok 3 numbers
Test #9:
score: 0
Accepted
time: 31ms
memory: 10216kb
input:
6 6 260666773 527612597 471926610 702232282 559007797 606173983 560573055 928117268 101411867 875949818 907478252 182117037
output:
0.00000000000000000000 0.96081957304526748970 0.03918042695473251029
result:
ok 3 numbers
Test #10:
score: 0
Accepted
time: 1ms
memory: 3736kb
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: 3852kb
input:
1 1 529429019 529428649
output:
1.00000000000000000000 0.00000000000000000000 0.00000000000000000000
result:
ok 3 numbers
Test #12:
score: 0
Accepted
time: 0ms
memory: 4024kb
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: 44ms
memory: 13596kb
input:
6 6 211213374 319527017 257080158 176742665 53109345 33822515 53109265 319527076 176743175 257080012 211212799 33822353
output:
0.42339995927640603567 0.31938658479080932784 0.25721345593278463650
result:
ok 3 numbers
Test #14:
score: 0
Accepted
time: 0ms
memory: 3908kb
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: 3732kb
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: 3736kb
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: 3688kb
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: 3728kb
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: 3732kb
input:
1 2 5 2 5
output:
0.00000000000000000000 0.00000000000000000000 1.00000000000000000000
result:
ok 3 numbers
Test #20:
score: 0
Accepted
time: 1ms
memory: 3904kb
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: 3912kb
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: 3856kb
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: 3672kb
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: 3740kb
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: 3976kb
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: 3960kb
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: 3736kb
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: 3856kb
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: 3664kb
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: 3960kb
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: 3664kb
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: 3980kb
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: 4104kb
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: 3980kb
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: 3896kb
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: 3856kb
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: 3668kb
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: 3912kb
input:
1 1 6 6
output:
0.00000000000000000000 0.00000000000000000000 1.00000000000000000000
result:
ok 3 numbers
Test #39:
score: 0
Accepted
time: 1ms
memory: 4084kb
input:
5 5 6 5 9 9 3 3 5 9 9 6
output:
0.29787037037037037036 0.27877314814814814815 0.42335648148148148149
result:
ok 3 numbers
Test #40:
score: 0
Accepted
time: 23ms
memory: 9148kb
input:
6 6 10 2 3 4 5 7 5 2 4 3 10 7
output:
0.25401045685442386833 0.19277370541838134430 0.55321583772719478740
result:
ok 3 numbers
Test #41:
score: -100
Wrong Answer
time: 256ms
memory: 51788kb
input:
7 7 7 6 8 6 7 3 9 7 6 9 8 7 3 6
output:
-0.00127878158906125648 -0.01602088708885229577 0.00255702457625466412
result:
wrong answer 1st numbers differ - expected: '0.3109138', found: '-0.0012788', error = '0.3121925'