oj.uz

Submission #259534

# Submission time Handle Problem Language Result Execution time Memory
259534 2020-08-08T01:39:01 Z dvdg6566 Fishing Game (RMI19_fishing) C++14
100 / 100
 355 ms 435320 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;

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

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

ll ask(ll ab,ll ac,ll bc,ll turn,ll 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;
    ll 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%MOD;
}

int main(){
    cin>>N>>T;
    memset(dp,-1,sizeof(dp));
    while(T--){
        for(ll i=0;i<3;++i)S[i].clear();
        for(ll i=0;i<2*N;++i){rdin(0);}
        for(ll i=0;i<2*N;++i){rdin(1);}
        for(ll i=0;i<2*N;++i){rdin(2);}
        ll ab=0;
        ll ac=0;
        ll 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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 435320 KB Output is correct
2 Correct 214 ms 435320 KB Output is correct
3 Correct 212 ms 435320 KB Output is correct
4 Correct 216 ms 435320 KB Output is correct
5 Correct 228 ms 435320 KB Output is correct
6 Correct 241 ms 435320 KB Output is correct
7 Correct 259 ms 435320 KB Output is correct
8 Correct 291 ms 435320 KB Output is correct
9 Correct 318 ms 435244 KB Output is correct
10 Correct 355 ms 435320 KB Output is correct