oj.uz

Submission #259136

# Submission time Handle Problem Language Result Execution time Memory
259136 2020-08-07T08:42:31 Z handlename Fishing Game (RMI19_fishing) C++17
50 / 100
 110 ms 98680 KB 
#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>>n>>t;
    memset(memo,-1,sizeof(memo));
    p=1e9+7;
    while (t--){
        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
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 48768 KB Output is correct
2 Correct 26 ms 48760 KB Output is correct
3 Correct 26 ms 48768 KB Output is correct
4 Correct 26 ms 48768 KB Output is correct
5 Correct 43 ms 48768 KB Output is correct
6 Runtime error 110 ms 98552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 97 ms 98552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 97 ms 98552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 95 ms 98552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 107 ms 98680 KB Execution killed with signal 11 (could be triggered by violating memory limits)