oj.uz

Submission #259532

# Submission time Handle Problem Language Result Execution time Memory
259532 2020-08-08T01:37:55 Z dvdg6566 Fishing Game (RMI19_fishing) C++14
10 / 100
 215 ms 217976 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MOD = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 210;
const ll BSIZ= 800;

int dp[MAXN][MAXN][MAXN][3][2];
int N,T,a,b;
set<int> S[MAXN];

void rdin(int x){
    cin>>a;
    if(S[x].find(a)!=S[x].end())S[x].erase(a);
    else S[x].insert(a);
}

int ask(int ab,int ac,int bc,int turn,int used){
    if(min({ab,ac,bc})<0)return 0;
    if(dp[ab][ac][bc][turn][used]!=-1)return dp[ab][ac][bc][turn][used];
    if(ab==0&&ac==0&&bc==0)return dp[ab][ac][bc][turn][used]=1;
    int ans=0;
    if(turn==0){
         // a is moving to b, can either move one of ab and one of ac
        if(ab==0&&ac==0){
            ans=ask(ab,ac,bc,1,used);
        }else{
            ans+=ab*ask(ab-1,ac,bc,1,1);
            ans+=ac*ask(ab,ac-1,bc+1,1,used);
        }
    }else if(turn==1){
        if(ab==0&&bc==0){
            ans=ask(ab,ac,bc,2,used);
        }else{
            ans+=bc*ask(ab,ac,bc-1,2,1);
            ans+=ab*ask(ab-1,ac+1,bc,2,used);
        }
    }else{
        if(ac==0&&bc==0){
            if(used)ans=ask(ab,ac,bc,0,0);
        }else{
            ans+=ac*ask(ab,ac-1,bc,0,0);
            if(used){
                ans+=bc*ask(ab+1,ac,bc-1,0,0);
            }
        }
    }
    // cerr<<ab<<' '<<ac<<' '<<bc<<' '<<turn<<' '<<used<<' '<<ans<<'\n';
    return dp[ab][ac][bc][turn][used]=ans;
}

int main(){
    cin>>N>>T;
    memset(dp,-1,sizeof(dp));
    while(T--){
        for(int i=0;i<3;++i)S[i].clear();
        for(int i=0;i<2*N;++i){rdin(0);}
        for(int i=0;i<2*N;++i){rdin(1);}
        for(int i=0;i<2*N;++i){rdin(2);}
        int ab=0;
        int ac=0;
        int bc=0;
        for(auto i:S[0])for(auto j:S[1])if(i==j)++ab;
        for(auto i:S[0])for(auto j:S[2])if(i==j)++ac;
        for(auto i:S[1])for(auto j:S[2])if(i==j)++bc;
        cout<<ask(ab,ac,bc,0,0)<<'\n';
    }
}

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 217848 KB Output is correct
2 Incorrect 112 ms 217848 KB Output isn't correct
3 Incorrect 114 ms 217848 KB Output isn't correct
4 Incorrect 111 ms 217848 KB Output isn't correct
5 Incorrect 125 ms 217848 KB Output isn't correct
6 Incorrect 134 ms 217764 KB Output isn't correct
7 Incorrect 147 ms 217864 KB Output isn't correct
8 Incorrect 168 ms 217976 KB Output isn't correct
9 Incorrect 189 ms 217848 KB Output isn't correct
10 Incorrect 215 ms 217848 KB Output isn't correct