QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#683527#5444. Tavern ChessSDNUyuqiRE 0ms0kbC++233.1kb2024-10-27 21:41:522024-10-27 21:41:53

Judging History

你现在查看的是最新测评结果

  • [2024-10-27 21:41:53]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-27 21:41:52]
  • 提交

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

output:


result: