oj.uz

답안 #543336

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
543336 2022-03-30T10:08:32 Z radal Fishing Game (RMI19_fishing) C++17
100 / 100
 162 ms 250348 KB 
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("unroll-loops")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 220,mod = 1e9+7,inf = 1e9+10,maxm = (1 << 18)+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k /= 2;
    }
    return z;
}
int n,T;
int dp[N][N][N][3][2];
pll vis[N*3];
void f(int i,int j,int k,int fl,int b){
    if (dp[i][j][k][fl][b] != -1) return;
    if (!i && !j && !k){
        dp[i][j][k][fl][b] = 1;
        return;
    }
    dp[i][j][k][fl][b] = 0;
    if (!fl){
        if (!i && !k){
            f(i,j,k,1,0);
            dp[i][j][k][0][0] = dp[i][j][k][1][0];
            return;
        }
        if (i){
            f(i-1,j,k,1,1);
            dp[i][j][k][fl][b] = 1ll*i*dp[i-1][j][k][1][1]%mod;
        }
        if (k){
            f(i,j+1,k-1,1,0);
            dp[i][j][k][0][0] = mkay(dp[i][j][k][0][0],1ll*k*dp[i][j+1][k-1][1][0]%mod);
        }
        return;
    }
    if (fl == 1){
        if (!i && !j){
            f(i,j,k,2,b);
            dp[i][j][k][1][b] = dp[i][j][k][2][b];
            return;
        }
        if (i){
            f(i-1,j,k+1,2,b);
            dp[i][j][k][fl][b] = 1ll*i*dp[i-1][j][k+1][2][b]%mod;
        }
        if (j){
            f(i,j-1,k,2,1);
            dp[i][j][k][fl][b] = mkay(dp[i][j][k][fl][b],1ll*j*dp[i][j-1][k][2][1]%mod);
        }
        return;
    }
    if (!j && !k){
        if (b == 1){
            f(i,j,k,0,0);
            dp[i][j][k][2][1] = dp[i][0][0][0][0];
        }
        else dp[i][j][k][2][0] = 0;
        return;
    }
    if (!b){
        if (!k){
            dp[i][j][k][2][0] = 0;
            return;
        }
        f(i,j,k-1,0,0);
        dp[i][j][k][2][0] = 1ll*k*dp[i][j][k-1][0][0]%mod;
        return;
    }
    if (k){
        f(i,j,k-1,0,0);
        dp[i][j][k][2][1] = 1ll*k*dp[i][j][k-1][0][0]%mod;
    }
    if (j){
        f(i+1,j-1,k,0,0);
        dp[i][j][k][2][1] = mkay(dp[i][j][k][2][1],1ll*dp[i+1][j-1][k][0][0]*j%mod);
    }
}
int main(){
    memset(dp,-1,sizeof dp);
    cin >> n >> T;
    int n2 = 2*n,n3 = 3*n;
    while (T--){
        rep(i,0,n3+1) vis[i] = {-1,-1};
        int t0 = 0,t1 = 0,t2 = 0;
        rep(j,0,3){
            rep(i,0,n2){
                int x;
                cin >> x;
                if (vis[x].X == -1) vis[x].X = j;
                else{
                    vis[x].Y = j;
                    if (vis[x].X == 0 && vis[x].Y  == 1) t0++;
                    else if (vis[x].X == 1 && vis[x].Y == 2) t1++;
                    else if (vis[x].X == 0 && vis[x].Y == 2) t2++;
                }
            }
        }
        f(t0,t1,t2,0,0);
        cout << dp[t0][t1][t2][0][0] << endl;
    }
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 250232 KB Output is correct
2 Correct 88 ms 250272 KB Output is correct
3 Correct 90 ms 250296 KB Output is correct
4 Correct 91 ms 250236 KB Output is correct
5 Correct 101 ms 250348 KB Output is correct
6 Correct 107 ms 250340 KB Output is correct
7 Correct 116 ms 250336 KB Output is correct
8 Correct 129 ms 250336 KB Output is correct
9 Correct 143 ms 250260 KB Output is correct
10 Correct 162 ms 250288 KB Output is correct