QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#683486 | #5444. Tavern Chess | SDNUyuqi | RE | 0ms | 0kb | C++23 | 3.5kb | 2024-10-27 21:25:36 | 2024-10-27 21:25:36 |
answer
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N=1+100;
ll a[2][N],h[2][N];
double an1,an2,an3;
unordered_set<int>la,lb;
set<pair<int,int>>A,B;
void dfs(int o,ll P)//1B0A
{
if(P>1e9)
{
return;
}
if(la.size()==0||lb.size()==0)
{
if(la.size()!=0)
{
cout<<1<<" "<<1.0/P<<endl;
an1+=1.0/P;
}
if(lb.size()!=0)
{
cout<<2<<" "<<1.0/P<<endl;
an2+=1.0/P;
}
return ;
}
if(o)
{
vector<pair<int,int>>BB;
while(B.size()&&!lb.count(B.begin()->second))
{
BB.push_back(*B.begin());
B.erase(B.begin());
}
if(B.size()==0)
{
return ;
}
auto t=*B.begin();
B.erase(B.begin());
int c=t.first,id=t.second;
auto laa=la;
for(auto i:laa)
{
h[1][id]-=a[0][i];
h[0][i]-=a[1][id];
int sign=la.size();
if(h[1][id]<=0)
{
lb.erase(id);
}
if(h[0][i]<=0)
{
la.erase(i);
}
B.insert({c+1,id});
dfs(o^1,P*sign);
B.erase({c+1,id});
if(h[1][id]<=0)
{
lb.insert(id);
}
if(h[0][i]<=0)
{
la.insert(i);
}
h[0][i]+=a[1][id];
h[1][id]+=a[0][i];
}
B.insert(t);
for(auto i:BB)
{
B.insert(i);
}
}
else
{
vector<pair<int,int>>AA;
while(A.size()&&!la.count(A.begin()->second))
{
AA.push_back(*A.begin());
A.erase(A.begin());
}
if(A.size()==0)
{
return ;
}
auto t=*A.begin();
A.erase(A.begin());
int c=t.first,id=t.second;
auto lbb=lb;
for(auto i:lbb)
{
h[0][id]-=a[1][i];
h[1][i]-=a[0][id];
int sign=lb.size();
if(h[0][id]<=0)
{
la.erase(id);
}
if(h[1][i]<=0)
{
lb.erase(i);
}
A.insert({c+1,id});
dfs(o^1,P*sign);
A.erase({c+1,id});
if(h[0][id]<=0)
{
la.insert(id);
}
if(h[1][i]<=0)
{
lb.insert(i);
}
h[1][i]+=a[0][id];
h[0][id]+=a[1][i];
}
A.insert(t);
for(auto i:AA)
{
A.insert(i);
}
}
}
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>a[0][i];
h[0][i]=a[0][i];
A.insert({0,i});
la.insert(i);
}
for(int i=0;i<m;i++)
{
cin>>a[1][i];
h[1][i]=a[1][i];
B.insert({0,i});
lb.insert(i);
}
if(n>m)
{
dfs(0,1);
}
else if(n<m)
{
dfs(1,1);
}
else
{
dfs(0,2);
dfs(1,2);
}
cout<<fixed<<setprecision(10)<<an1<<" "<<an2<<" "<<1-an1-an2<<endl;
system("pause");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Dangerous Syscalls
input:
2 3 2 5 3 4 1