Submission #287173

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
287173	2020-08-31T13:10:07 Z	eohomegrownapps	Fishing Game (RMI19_fishing)	C++14	100 / 100	123 ms	63352 KB

fishing

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll m = 1e9+7;

ll dpv[201][201][201];
//ab, ac, bc
ll dp(int ab, int ac, int bc, int curplayer, bool discard){
    //cout<<ab<<' '<<ac<<' '<<bc<<' '<<curplayer<<' '<<discard<<'\n';
    if (curplayer==0){
        if (ab==0&&ac==0&&bc==0){
            return 1;
        }
        if (discard==false){
            return 0;
        }
        if (dpv[ab][ac][bc]!=-1){
            return dpv[ab][ac][bc];
        }
        discard = false;
    }
    ll ans = 0;
    if (curplayer==0){
        if (ab==0 && ac==0){
            return dpv[ab][ac][bc]=dp(ab,ac,bc,1,discard);
        }
        if (ab>0){
            ans+=(ab*dp(ab-1,ac,bc,1,true));
            ans%=m;
        }
        if (ac>0){
            ans+=(ac*dp(ab,ac-1,bc+1,1,discard));
            ans%=m;
        }
        return dpv[ab][ac][bc]=ans;
    } else if (curplayer==1){
        if (ab==0 && bc==0){
            return dp(ab,ac,bc,2,discard);
        }
        if (bc>0){
            ans+=(bc*dp(ab,ac,bc-1,2,true));
            ans%=m;
        }
        if (ab>0){
            ans+=(ab*dp(ab-1,ac+1,bc,2,discard));
            ans%=m;
        }
        return ans;
    } else if (curplayer==2){
        if (ac==0 && bc==0){
            return dp(ab,ac,bc,0,discard);
        }
        if (ac>0){
            ans+=(ac*dp(ab,ac-1,bc,0,true));
            ans%=m;
        }
        if (bc>0){
            ans+=(bc*dp(ab+1,ac,bc-1,0,discard));
            ans%=m;
        }
        return ans;
    } else {
        assert(1==0);
    }
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n,t;
    cin>>n>>t;
    for (int x = 0; x<=2*n; x++){
        for (int y = 0; y<=2*n; y++){
            for (int z = 0; z<=2*n; z++){
                dpv[x][y][z]=-1;
            }
        }
    }
    dpv[0][0][0]=1;
    for (int i = 0; i<t; i++){
        vector<vector<int>> cardowners(3*n);
        for (int p = 0; p<3; p++){
            for (int x = 0; x<2*n; x++){
                //player a's hand
                int c;
                cin>>c;
                c--;
                cardowners[c].push_back(p);
            }
        }
        ll ab = 0;
        ll bc = 0;
        ll ac = 0;
        for (int i = 0; i<3*n; i++){
            if (cardowners[i][0]==0&&cardowners[i][1]==1){
                ab++;
            }
            if (cardowners[i][0]==0&&cardowners[i][1]==2){
                ac++;
            }
            if (cardowners[i][0]==1&&cardowners[i][1]==2){
                bc++;
            }
        }
        cout<<dp(ab,ac,bc,0,true)<<'\n';
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	1152 KB	Output is correct
4	Correct	3 ms	3072 KB	Output is correct
5	Correct	19 ms	16768 KB	Output is correct
6	Correct	31 ms	23808 KB	Output is correct
7	Correct	46 ms	32128 KB	Output is correct
8	Correct	65 ms	41828 KB	Output is correct
9	Correct	93 ms	52732 KB	Output is correct
10	Correct	123 ms	63352 KB	Output is correct