Submission #198089

#	Time	Username	Problem	Language	Result	Execution time	Memory
198089		model_code	Fishing Game (RMI19_fishing)	C++17	20 / 100	105 ms	55800 KiB

fishing

/**
* user:  gospodinov-b8b
* fname: Antani
* lname: Gospodinov
* task:  fishing
* score: 20.0
* date:  2019-10-11 08:22:01.095417
*/
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
using namespace std;
const int N = 35;
const int MOD = 1e9 + 7;

int add(int x, int y)
{
    return (x + MOD + y) % MOD;
}
int mul(int x, int y)
{
    return (1LL * add(0, x) * add(0, y)) % MOD;
}

int n;
int dp[3 * N][3 * N][3 * N][3][2];

int solve(int shared_AB, int shared_BC, int shared_CA, int turn, bool discarded)
{
    int A = shared_AB + shared_CA, B = shared_AB + shared_BC, C = shared_BC + shared_CA;
    //cout << A << " " << B << " " << C << " " << turn << " " << discarded << endl;
    if(dp[shared_AB][shared_BC][shared_CA][turn][discarded] != -1)
        return dp[shared_AB][shared_BC][shared_CA][turn][discarded];

    if(shared_AB + shared_BC + shared_CA == 0)
        return 1;

    int state = 0;

    if(turn == 0 && shared_CA)
        state = add(state, mul(shared_CA, solve(shared_AB, shared_BC + 1, shared_CA - 1, 1, discarded)));
    if(turn == 1 && shared_AB)
        state = add(state, mul(shared_AB, solve(shared_AB - 1, shared_BC, shared_CA + 1, 2, discarded)));
    if(turn == 2 && shared_BC && discarded)
        state = add(state, mul(shared_BC, solve(shared_AB + 1, shared_BC - 1, shared_CA, 0, false)));

    if(turn == 0 && shared_AB)
        state = add(state, mul(shared_AB, solve(shared_AB - 1, shared_BC, shared_CA, 1, true)));
    if(turn == 1 && shared_BC)
        state = add(state, mul(shared_BC, solve(shared_AB, shared_BC - 1, shared_CA, 2, true)));
    if(turn == 2 && shared_CA)
        state = add(state, mul(shared_CA, solve(shared_AB, shared_BC, shared_CA - 1, 0, false)));

    if(turn == 0 && A == 0)
        state = add(state, solve(shared_AB, shared_BC, shared_CA, 1, discarded));
    if(turn == 1 && B == 0)
        state = add(state, solve(shared_AB, shared_BC, shared_CA, 2, discarded));
    if(turn == 2 && C == 0 && discarded)
        state = add(state, solve(shared_AB, shared_BC, shared_CA, 0, false));

    return dp[shared_AB][shared_BC][shared_CA][turn][discarded] = state;
}


int cnt[3][305];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    memset(dp, -1, sizeof(dp));

    int tests;
    cin >> n >> tests;
    while(tests--)
    {
        memset(cnt, 0, sizeof(cnt));
        for(int i = 0; i < 3; i++)
            for(int j = 1; j <= 2 * n; j++)
            {
                int x; cin >> x;
                cnt[i][x] = (cnt[i][x] + 1) % 2;
            }

        int shared_ab = 0, shared_bc = 0, shared_ca = 0;
        for(int j = 1; j <= 3 * n; j++)
        {
            if(cnt[0][j] && cnt[1][j])
                shared_ab++;
            if(cnt[1][j] && cnt[2][j])
                shared_bc++;
            if(cnt[2][j] && cnt[0][j])
                shared_ca++;
        }

        cout << solve(shared_ab, shared_bc, shared_ca, 0, 0) << endl;
    }


    return 0;
}

/*

1 1
1 3
1 2
2 3


*/

• Subtask 1: 20 / 100