oj.uz

Submission #649725

# Submission time Handle Problem Language Result Execution time Memory
649725 2022-10-11T09:21:57 Z boris_mihov Fishing Game (RMI19_fishing) C++17
0 / 100
 2000 ms 1516 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[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()
{
    std::fill(&where[0][0], &where[3*n][1] + 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Execution timed out 2068 ms 980 KB Time limit exceeded
4 Execution timed out 2076 ms 864 KB Time limit exceeded
5 Execution timed out 2076 ms 948 KB Time limit exceeded
6 Execution timed out 2074 ms 652 KB Time limit exceeded
7 Execution timed out 2082 ms 1008 KB Time limit exceeded
8 Execution timed out 2087 ms 764 KB Time limit exceeded
9 Execution timed out 2083 ms 1516 KB Time limit exceeded
10 Execution timed out 2076 ms 1460 KB Time limit exceeded