Submission #649739

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
649739	2022-10-11T09:38:54 Z	boris_mihov	Fishing Game (RMI19_fishing)	C++17	100 / 100	1476 ms	360532 KB

fishing

#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

#	Verdict	Execution time	Memory	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