QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#683527 | #5444. Tavern Chess | SDNUyuqi | RE | 0ms | 0kb | C++23 | 3.1kb | 2024-10-27 21:41:52 | 2024-10-27 21:41:53 |
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;
set<int>la,lb;
set<pair<int,int>>A,B;
void dfs(int o,ll P)//1B0A
{
if(la.size()==0||lb.size()==0)
{
if(la.size()!=0)
{
an1+=1.0/P;
}
if(lb.size()!=0)
{
an2+=1.0/P;
}
return ;
}
if(o)
{
auto BB=B;
while(B.size()&&!lb.count(B.begin()->second))
{
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);
B=BB;
}
else
{
auto AA=A;
while(A.size()&&!la.count(A.begin()->second))
{
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);
A=AA;
}
}
int main()
{
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;
}
詳細信息
Test #1:
score: 0
Dangerous Syscalls
input:
2 3 2 5 3 4 1