Submission #259111

#	Time	Username	Problem	Language	Result	Execution time	Memory
259111		handlename	Fishing Game (RMI19_fishing)	C++17	0 / 100	113 ms	98552 KiB

fishing

#include <bits/stdc++.h>
//#include "bingo.h"
using namespace std;
#define pb push_back
#define mp make_pair
int n,t,p;
long long memo[101][101][101][3][2];
long long dp(int a,int b,int c,int guy,bool use){
    //a is 0 and 1, b is 0 and 2, c is 1 and 2
    if (a<0 || b<0 || c<0) return 0;
    if (a==0 && b==0 && c==0) return 1;
    if (memo[a][b][c][guy][use]!=-1){
        return memo[a][b][c][guy][use];
    }
    long long res=0;
    if (guy==0){
        if (a+b==0){
            res=dp(a,b,c,1,use);
        }
        else {
            res+=dp(a-1,b,c,1,true)*a;
            res+=dp(a,b-1,c+1,1,use)*b;
        }
    }
    else if (guy==1){
        if (a+c==0){
            res=dp(a,b,c,2,use);
        }
        else {
            res+=dp(a,b,c-1,2,true)*c;
            res+=dp(a-1,b+1,c,2,use)*a;
        }
    }
    else {
        if (b+c==0){
            if (use==false) res=0;
            else res=dp(a,b,c,0,false);
        }
        else {
            res+=dp(a,b-1,c,0,false)*b;
            if (use) res+=dp(a+1,b,c-1,0,false)*c;
        }
    }
    //cout<<a<<' '<<b<<' '<<c<<' '<<guy<<' '<<use<<' '<<res<<'\n';
    return memo[a][b][c][guy][use]=res%p;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>t;
    memset(memo,-1,sizeof(memo));
    p=1e9+7;
    while (t--){
        cin>>n;
        set<int> arr[3];
        for (int i=0;i<3;i++){
            for (int j=0;j<n*2;j++){
                int x;
                cin>>x;
                if (arr[i].find(x)!=arr[i].end()){
                    arr[i].erase(x);
                }
                else arr[i].insert(x);
            }
        }
        int a=0,b=0,c=0;
        //a is 0 and 1, b is 0 and 2, c is 1 and 2
        for (auto i:arr[0]){
            if (arr[1].find(i)!=arr[1].end()){
                a++;
            }
            else b++;
        }
        for (auto i:arr[1]){
            if (arr[2].find(i)!=arr[2].end()){
                c++;
            }
        }
        //cout<<a<<' '<<b<<' '<<c<<'\n';
        cout<<dp(a,b,c,0,false)<<'\n';
    }
}

• Subtask 1: 0 / 100