oj.uz

답안 #649739

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
649739 2022-10-11T09:38:54 Z boris_mihov Fishing Game (RMI19_fishing) C++17
100 / 100
 1476 ms 360532 KB 
#include <algorithm>
#include <iostream>
#include <tgmath.h>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>

typedef long long llong; 
const int MAXN = 100 + 10;
const int MOD  = 1e9 + 7;
const int INF  = 1e9;

int n, t;
int fact[3*MAXN];
int where[3*MAXN][2];
int dp[3*MAXN][3*MAXN][3*MAXN][3][2];
bool bl[3*MAXN][3*MAXN][3*MAXN][3][2];
int f(int cntAB, int cntAC, int cntBC, int turn, bool discarded)
{
    if (cntAB < 0 || cntAC < 0 || cntBC < 0) return 0;
    if (cntAB == 0 && cntAC == 0) return fact[cntBC];
    if (cntAB == 0 && cntBC == 0) return fact[cntAC];
    if (cntAC == 0 && cntBC == 0) return fact[cntAB];
    if (bl[cntAB][cntAC][cntBC][turn][discarded]) return dp[cntAB][cntAC][cntBC][turn][discarded];
    bl[cntAB][cntAC][cntBC][turn][discarded] = 1;

    llong res = 0;
    if (turn == 0)
    {
        res += 1LL * f(cntAB - 1, cntAC, cntBC, 1, 1) * cntAB;
        res += 1LL * f(cntAB, cntAC - 1, cntBC + 1, 1, 0) * cntAC;
    }

    if (turn == 1)
    {
        res += 1LL * f(cntAB, cntAC, cntBC - 1, 2, 1) * cntBC;
        res += 1LL * f(cntAB - 1, cntAC + 1, cntBC, 2, discarded) * cntAB;
    }

    if (turn == 2)
    {
        res += 1LL * f(cntAB, cntAC - 1, cntBC, 0, 0) * cntAC;
        if (discarded)
        {
            res += 1LL * f(cntAB + 1, cntAC, cntBC - 1, 0, 0) * cntBC;
        }
    }

    return dp[cntAB][cntAC][cntBC][turn][discarded] = res % MOD;
}

void solve()
{
    int cntAB = 0;
    int cntAC = 0;
    int cntBC = 0;
    for (int i = 1 ; i <= 3*n ; ++i)
    {
        if (where[i][0] == 1 && where[i][1] == 2) cntAB++;
        if (where[i][0] == 1 && where[i][1] == 3) cntAC++;
        if (where[i][0] == 2 && where[i][1] == 3) cntBC++;
    }

    std::cout << f(cntAB, cntAC, cntBC, 0, 0) << '\n';
}

void read()
{
    for (int i = 1 ; i <= 3*n ; ++i)
    {
        where[i][0] = where[i][1] = 0;
    }

    int curr;
    for (int i = 1 ; i <= 2*n ; ++i)
    {
        std::cin >> curr;
        if (where[curr][0] == 0) where[curr][0] = 1;
        else where[curr][1] = 1;
    }

    for (int i = 1 ; i <= 2*n ; ++i)
    {
        std::cin >> curr;
        if (where[curr][0] == 0) where[curr][0] = 2;
        else where[curr][1] = 2;
    }

    for (int i = 1 ; i <= 2*n ; ++i)
    {
        std::cin >> curr;
        if (where[curr][0] == 0) where[curr][0] = 3;
        else where[curr][1] = 3;
    }
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIO();
    std::cin >> n >> t;

    fact[0] = 1;
    for (int i = 1 ; i <= 3*n ; ++i) fact[i] = (1LL * fact[i-1] * i) % MOD;
    for (int sum = 0 ; sum <= 3*n ; ++sum)
    {
        for (int cntAB = 0 ; cntAB <= sum ; ++cntAB)
        {
            for (int cntAC = 0 ; cntAC <= sum - cntAB ; ++cntAC)
            {
                f(cntAB, cntAC, sum - cntAB - cntAC, 2, 0);
                f(cntAB, cntAC, sum - cntAB - cntAC, 2, 1);
                f(cntAB, cntAC, sum - cntAB - cntAC, 1, 1);
                f(cntAB, cntAC, sum - cntAB - cntAC, 1, 0);
                f(cntAB, cntAC, sum - cntAB - cntAC, 0, 1);
                f(cntAB, cntAC, sum - cntAB - cntAC, 0, 0);
            }
        }
    }

    while (t--)
    {
        read();
        solve();
    }

    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 3 ms 3540 KB Output is correct
4 Correct 13 ms 12796 KB Output is correct
5 Correct 144 ms 83156 KB Output is correct
6 Correct 250 ms 122712 KB Output is correct
7 Correct 445 ms 171112 KB Output is correct
8 Correct 732 ms 228064 KB Output is correct
9 Correct 1079 ms 294044 KB Output is correct
10 Correct 1476 ms 360532 KB Output is correct