Submission #476217

# Submission time Handle Problem Language Result Execution time Memory
476217 2021-09-25T11:08:42 Z iulia13 Fishing Game (RMI19_fishing) C++14
100 / 100
1821 ms 54592 KB
#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int N = 305;
const int mod = 1e9 + 7;
int dp[N][N][N];
void adun(int &a, int b)
{
    a += b;
    if (a >= mod)
        a -= mod;
}
int inm(int a, int b)
{
    ll c = 1ll * a * b;
    c %= mod;
    return c;
}
///dp[i][j][k] = nr moduri daca a,b au i in comun
///                             b,c au j in comun
///                             c,a au k in comun
/**
op
1) a NU are ce sa ii dea lui b => a = 0 => i + k = 0
2) a -> b una pe care o are b => i posibilitati, i--
3) a -> b una pe care o are c => k posibilitati, j++ k--
tb macar o op 2 ca s sa scada
**/
int pos;
void op1(int i, int j, int k)
{
    if (i + k != 0)
        pos = 0;
}
void op2(int &i, int j, int k)
{
    pos *= i;
    i--;
}
void op3(int i, int &j, int &k)
{
    pos *= k;
    j++;
    k--;
}
int vc[3][N];
int x[3][3];
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, t;
    cin >> n >> t;
    dp[0][0][0] = 1;
    for (int s = 1; s <= 6 * n; s++)
        for (int i = 0; i <= 3 * n && i <= s; i++)
            for (int j = 0; j <= 3 * n && j + i <= s; j++)
            {
                int k = s - i - j;
                if (i + k > 3 * n || i + j > 3 * n || i + k > 3 * n)
                    continue;
                for (int ab = 1; ab <= 3; ab++)
                    for (int bc = 1; bc <= 3; bc++)
                        for (int ca = 1; ca <= 3; ca++)
                        {
                            if (ab != 2 && bc != 2 && ca != 2)
                                continue;
                            pos = 1;
                            int I = i, J = j, K = k;
                            if (ab == 1)
                                op1(I, J, K);
                            else
                            if (ab == 2)
                                op2(I, J, K);
                            else
                                op3(I, J, K);
if (I < 0 || J < 0 || K < 0)
                                continue;
                            if (!pos)
                                continue;
                            if (bc == 1)
                                op1(J, K, I);
                            else
                            if (bc == 2)
                                op2(J, K, I);
                            else
                                op3(J, K, I);
if (I < 0 || J < 0 || K < 0)
                                continue;
                            if (!pos)
                                continue;
                            if (ca == 1)
                                op1(K, I, J);
                            else
                            if (ca == 2)
                                op2(K, I, J);
                            else
                                op3(K, I, J);
                            if (I < 0 || J < 0 || K < 0)
                                continue;
                            if (!pos)
                                continue;
                            adun(dp[i][j][k], inm(pos, dp[I][J][K]));
                        }

            }
    while(t--)
    {
        for (int i = 0; i < 3; i++)
            for (int j = 1; j <= 3 * n; j++)
                vc[i][j] = 0;
        for (int i = 0; i < 3; i++)
            for (int j = 1; j <= 2 * n; j++)
            {
                int nr;
                cin >> nr;
                vc[i][nr] = 1;
            }

        for (int i = 0; i < 3; i++)
            for (int j = i + 1; j < 3; j++)
            {
                x[i][j] = 0;
                for (int k = 1; k <= 3 * n; k++)
                    if (vc[i][k] && vc[j][k])
                        x[i][j]++;
            }
        cout << dp[x[0][1]][x[1][2]][x[0][2]] << '\n';
    }
    return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 16 ms 2800 KB Output is correct
5 Correct 240 ms 14544 KB Output is correct
6 Correct 402 ms 20572 KB Output is correct
7 Correct 747 ms 27824 KB Output is correct
8 Correct 948 ms 35952 KB Output is correct
9 Correct 1364 ms 45268 KB Output is correct
10 Correct 1821 ms 54592 KB Output is correct