Submission #331852

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
331852	2020-11-30T12:43:00 Z	alextodoran	Fishing Game (RMI19_fishing)	C++17	0 / 100	2000 ms	327116 KB

fishing

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 102;
const int F_MAX = 4000002;

int n, t;

int dp[3 * N_MAX][3 * N_MAX][3 * N_MAX];

bool a[3 * N_MAX], b[3 * N_MAX], c[3 * N_MAX];

int f (int i, int j, int k)
{
    return k + 101 * j + 101 * 101 * i;
}

vector <int> edges[F_MAX];

int deg[F_MAX];

vector <int> order;

queue <int> q;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> t;
    for(int i = 0; i <= 3 * n; i++)
        for(int j = 0; j <= 3 * n; j++)
            for(int k = 0; k <= 3 * n; k++)
            {
                if(i == 0 && j == 0 && k == 0)
                    continue;
                if(i > 0)
                {
                    edges[f(j, k, i - 1)].push_back(f(i, j, k));
                    deg[f(i, j, k)]++;
                }
                if(k > 0)
                {
                    edges[f(j + 1, k - 1, i)].push_back(f(i, j, k));
                    deg[f(i, j, k)]++;
                }
            }
    for(int u = 0; u < f(3 * n, 3 * n, 3 * n); u++)
        if(deg[u] == 0 && u % 101 <= 3 * n && u / 101 % 101 <= 3 * n && u / 101 / 10 <= 3 * n)
            q.push(u);
    while(!q.empty())
    {
        int u = q.front();
        order.push_back(u);
        q.pop();
        for(int v : edges[u])
        {
            deg[v]--;
            if(deg[v] == 0)
                q.push(v);
        }
    }
    dp[0][0][0] = 1;
    for(int u : order)
    {
        int k = u % 101;
        int j = u / 101 % 101;
        int i = u / 101 / 101;
        if(i == 0 && j == 0 && k == 0)
        {
            dp[i][j][k] = 1;
            continue;
        }
        dp[i][j][k] = 0;
        if(i > 0)
            dp[i][j][k] += dp[j][k][i - 1] * i;
        if(k > 0)
            dp[i][j][k] += dp[j + 1][k - 1][i] * k;
    }
    while(t--)
    {
        for(int i = 1; i <= n * 3; i++)
            a[i] = b[i] = c[i] = false;
        for(int i = 1; i <= n * 2; i++)
        {
            int card;
            cin >> card;
            a[card] = true;
        }
        for(int i = 1; i <= n * 2; i++)
        {
            int card;
            cin >> card;
            b[card] = true;
        }
        for(int i = 1; i <= n * 2; i++)
        {
            int card;
            cin >> card;
            c[card] = true;
        }
        int I = 0, J = 0, K = 0;
        for(int i = 1; i <= n * 3; i++)
            I += (a[i] && b[i]);
        for(int i = 1; i <= n * 3; i++)
            J += (b[i] && c[i]);
        for(int i = 1; i <= n * 3; i++)
            K += (c[i] && a[i]);
        cout << dp[I][J][K] << "\n";
    }
    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	64 ms	94316 KB	Output isn't correct
2	Incorrect	67 ms	94444 KB	Output isn't correct
3	Incorrect	82 ms	96048 KB	Output isn't correct
4	Incorrect	104 ms	103660 KB	Output isn't correct
5	Incorrect	758 ms	155756 KB	Output isn't correct
6	Incorrect	1093 ms	179536 KB	Output isn't correct
7	Incorrect	1610 ms	218872 KB	Output isn't correct
8	Execution timed out	2108 ms	295640 KB	Time limit exceeded
9	Execution timed out	2115 ms	327116 KB	Time limit exceeded
10	Execution timed out	2109 ms	326008 KB	Time limit exceeded