/**
* 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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
27512 KB |
Output is correct |
| 2 |
Correct |
25 ms |
27512 KB |
Output is correct |
| 3 |
Incorrect |
25 ms |
27512 KB |
Output isn't correct |
| 4 |
Incorrect |
26 ms |
27516 KB |
Output isn't correct |
| 5 |
Incorrect |
47 ms |
27512 KB |
Output isn't correct |
| 6 |
Runtime error |
92 ms |
55680 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
105 ms |
55640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
93 ms |
55676 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
98 ms |
55664 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
102 ms |
55800 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
