Submission #649727

#	Time	Username	Problem	Language	Result	Execution time	Memory
649727		boris_mihov	Fishing Game (RMI19_fishing)	C++17	0 / 100	135 ms	128736 KiB

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 where[3*MAXN][2];
int dp[2*MAXN][2*MAXN][2*MAXN][3][2];
bool bl[2*MAXN][2*MAXN][2*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 && cntBC == 0) return 1;
    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;

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

    return 0;
}

• Subtask 1: 0 / 100