답안 #259135

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
259135 2020-08-07T08:41:29 Z handlename Fishing Game (RMI19_fishing) C++17
50 / 100
57 ms 49552 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[101][101][101][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]!=-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;
            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;
    memset(memo,-1,sizeof(memo));
    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';
    }
}
# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 24576 KB Output is correct
2 Correct 13 ms 24576 KB Output is correct
3 Correct 16 ms 24576 KB Output is correct
4 Correct 14 ms 24576 KB Output is correct
5 Correct 23 ms 24576 KB Output is correct
6 Runtime error 53 ms 49528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 56 ms 49528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 57 ms 49536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 53 ms 49552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 55 ms 49528 KB Execution killed with signal 11 (could be triggered by violating memory limits)