oj.uz

Submission #259139

# Submission time Handle Problem Language Result Execution time Memory
259139 2020-08-07T08:44:40 Z handlename Fishing Game (RMI19_fishing) C++17
100 / 100
 215 ms 124408 KB 
#include <bits/stdc++.h>
//#include "bingo.h"
using namespace std;
#define pb push_back
#define mp make_pair
long long n,t,p;
int memo[301][301][301][3][2];
long long dp(int ab,int ac,int bc,int guy,bool use){
    if (ab+ac+bc==0) return 1;
    if (guy==0){
        if (!use) return 0;
        use=false;
    }
    if (memo[ab][ac][bc][guy][use]!=0){
        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;
            res%=p;
            if (ac>0) res+=dp(ab,ac-1,bc+1,1,use)*(long long) ac;
            res%=p;
        }
    }
    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;
            res%=p;
            if (ab>0) res+=dp(ab-1,ac+1,bc,2,use)*(long long) ab;
            res%=p;
        }
    }
    if (guy==2) {
        if (ac+bc==0){
            res=dp(ab,ac,bc,0,use);
        }
        else {
            if (ac>0) res+=dp(ab,ac-1,bc,0,true)*(long long) ac;
            res%=p;
            if (bc>0) res+=dp(ab+1,ac,bc-1,0,use)*(long long) bc;
            res%=p;
        }
    }
    //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>>n>>t;
    p=1e9+7;
    while (t--){
        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;
        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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 1 ms 1408 KB Output is correct
4 Correct 4 ms 4352 KB Output is correct
5 Correct 30 ms 27384 KB Output is correct
6 Correct 55 ms 40696 KB Output is correct
7 Correct 73 ms 57336 KB Output is correct
8 Correct 117 ms 77436 KB Output is correct
9 Correct 166 ms 100728 KB Output is correct
10 Correct 215 ms 124408 KB Output is correct