oj.uz

Submission #649736

# Submission time Handle Problem Language Result Execution time Memory
649736 2022-10-11T09:35:16 Z boris_mihov Fishing Game (RMI19_fishing) C++17
0 / 100
 1440 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 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 && 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;

    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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Incorrect 1 ms 724 KB Output isn't correct
3 Incorrect 3 ms 3540 KB Output isn't correct
4 Incorrect 11 ms 12884 KB Output isn't correct
5 Incorrect 125 ms 83140 KB Output isn't correct
6 Incorrect 258 ms 122744 KB Output isn't correct
7 Incorrect 451 ms 171128 KB Output isn't correct
8 Incorrect 696 ms 228064 KB Output isn't correct
9 Incorrect 1041 ms 293796 KB Output isn't correct
10 Incorrect 1440 ms 360532 KB Output isn't correct