oj.uz

Submission #259125

# Submission time Handle Problem Language Result Execution time Memory
259125 2020-08-07T08:31:58 Z handlename Fishing Game (RMI19_fishing) C++17
0 / 100
 28 ms 48768 KB 
#include <bits/stdc++.h>
//#include "bingo.h"
using namespace std;
#define pb push_back
#define mp make_pair
long long n,t,p;
long long memo[101][101][101][3][2];
long long dp(int ab,int ac,int bc,int guy,bool use){
    //a is 0 and 1, b is 0 and 2, c is 1 and 2
    if (ab==0 && ac==0 && bc==0) return 1;
    if (guy==0){
        if (!use) return 0;
        use=false;
    }
    if (memo[ab][ac][bc][guy][use]!=-1){
        return memo[ab][ac][bc][guy][use];
    }
    long long res=0;
    if (guy==0){
        if (ab+ac==0){
            res=dp(ab,ac,bc,1,use);
        }
        else {
            if (ab>0) res+=dp(ab-1,ac,bc,1,true)*(long long) ab;
            if (ac>0) res+=dp(ab,ac-1,bc+1,1,use)*(long long) ac;
        }
    }
    else if (guy==1){
        if (ab+bc==0){
            res=dp(ab,ac,bc,2,use);
        }
        else {
            if (bc>0) res+=dp(ab,ac,bc-1,2,true)*(long long) bc;
            if (ab>0) res+=dp(ab-1,ac+1,bc,2,use)*(long long) ab;
        }
    }
    else {
        if (ac+bc==0){
            res=dp(ab,ac,bc,0,use);
        }
        else {
            if (ac>0) res+=dp(ab,ac-1,bc,0,false)*(long long) ac;
            if (bc>0) res+=dp(ab+1,ac,bc-1,0,false)*(long long) bc;
        }
    }
    //cout<<a<<' '<<b<<' '<<c<<' '<<guy<<' '<<use<<' '<<res<<'\n';
    return memo[ab][ac][bc][guy][use]=res%p;
}
pair<int,int> arr[301];
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;
        for (int i=1;i<=n*3;i++){
            arr[i]=mp(-1,-1);
        }
        for (int i=0;i<3;i++){
            for (int j=0;j<n*2;j++){
                int x;
                cin>>x;
                if (arr[x].first==-1) arr[x].first=i;
                else arr[x].second=i;
            }
        }
        int ab=0,ac=0,bc=0;
        //a is 0 and 1, b is 0 and 2, c is 1 and 2
        for (int i=1;i<=n*3;i++){
            if (arr[i].first==arr[i].second) continue;
            if (arr[i].first>arr[i].second){
                swap(arr[i].first,arr[i].second);
            }
            if (arr[i]==mp(0,1)) ab++;
            else if (arr[i]==mp(0,2)) ac++;
            else bc++;
        }
        //cout<<a<<' '<<b<<' '<<c<<'\n';
        cout<<dp(ab,ac,bc,0,true)<<'\n';
    }
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 48768 KB Output isn't correct
2 Incorrect 24 ms 48760 KB Output isn't correct
3 Incorrect 24 ms 48768 KB Output isn't correct
4 Incorrect 25 ms 48768 KB Output isn't correct
5 Incorrect 25 ms 48760 KB Output isn't correct
6 Incorrect 25 ms 48768 KB Output isn't correct
7 Incorrect 25 ms 48760 KB Output isn't correct
8 Incorrect 25 ms 48760 KB Output isn't correct
9 Incorrect 27 ms 48768 KB Output isn't correct
10 Incorrect 28 ms 48760 KB Output isn't correct