#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;
int mod = 1e9 + 7;
int main(){
int n, q;
cin >> n >> q;
int N = 3 * n;
vector<vector<vector<ll>>> dp(N + 1, vector<vector<ll>>(N + 1, vector<ll>(N + 1)));
vector<vector<vector<ll>>> vis(N + 1, vector<vector<ll>>(N + 1, vector<ll>(N + 1)));
vis[0][0][0] = 1;
dp[0][0][0] = 1;
auto f = [&](vector<int> c, int x, int y, int z) -> pair<ll, vector<int>>{
if(x == 0 && y == 0 && z == 0) return make_pair(0, c);
ll coef = 1;
if(c[0] == 0 || c[1] == 0 || c[2] == 0){
if(x == 0 && y == 1 && z == 0 && c[0] == 0 && c[1] == 0 && c[2] == 1){
coef = 1;
c[2]--;
return make_pair(coef, c);
}
if(x == 0 && y == 1 && z == 0 && c[0] == 0 && c[1] == 0){
coef = c[2] * (c[2] - 1);
c[0] = 1;
c[2] -= 2;
return make_pair(coef, c);
}
if(x == 0 && y == 1 && z == 0 && c[0] == 0 && c[2] == 0){
coef = 1;
c[1] -= 1;
return make_pair(coef, c);
}
if(x == 0 && y == 1 && z == 1 && c[0] == 0 && c[2] == 0){
coef = c[1] * (c[1] - 1);
c[1] -= 2;
return make_pair(coef, c);
}
if(x == 1 && y == 0 && z == 0 && c[1] == 0 && c[2] == 0 && c[0] == 1){
c[0]--;
return make_pair(1, c);
}
if(x == 1 && y == 0 && z == 1 && c[1] == 0 && c[2] == 0){
coef = c[0] * (c[0] - 1);
c[0] -= 2;
return make_pair(coef, c);
}
return make_pair(0, c);
}
if(x == 0){
coef *= c[1];
c[1]--;
c[2]++;
}
if(x == 1){
if(c[0] <= 0) return make_pair(0, c);
coef *= c[0];
c[0]--;
}
if(y == 0){
coef *= c[0];
c[0]--;
c[1]++;
}
if(y == 1){
if(c[2] <= 0) return make_pair(0, c);
coef *= c[2];
c[2]--;
}
if(z == 0){
coef *= c[2];
c[2]--;
c[0]++;
}
if(z == 1){
if(c[1] <= 0) return make_pair(0, c);
coef *= c[1];
c[1]--;
}
return make_pair(coef, c);
};
function<ll(int, int, int)> find_dp = [&](int a, int b, int d){
if(a < 0 || b < 0 || d < 0) return 0ll;
if(vis[a][b][d]) return dp[a][b][d];
vector<int> c = {a, b, d};
for(int x = 0; x < 2; x++) for(int y = 0; y < 2; y++) for(int z = 0; z < 2; z++){
auto hold = f(c, x, y, z);
ll coef = hold.first;
vector<int> tmp = hold.second;
if(coef != 0) dp[a][b][d] += coef * find_dp(tmp[0], tmp[1], tmp[2]);
}
// dp[a][b][d] += c[1] * c[0] * c[1] * find_dp(c[0] - 1, c[1] - 1, c[2] + 1); // 001
// dp[a][b][d] += c[1] * (c[2] + 1) * (c[2]) * find_dp(c[0] + 1, c[1] - 1, c[2] - 1); // 010
// dp[a][b][d] += c[1] * (c[2] + 1) * (c[1] - 1) * find_dp(c[0], c[1] - 2, c[2]); // 011
// dp[a][b][d] += c[0] * (c[0] - 1) * (c[2]) * find_dp(c[0] - 1, c[1] + 1, c[2] - 1); // 100
// dp[a][b][d] += c[0] * (c[0] - 1) * (c[1] + 1) * find_dp(c[0] - 2, c[1], c[2]); // 101
// dp[a][b][d] += c[0] * c[2] * (c[2] - 1) * find_dp(c[0], c[1], c[2] - 2); // 110
// dp[a][b][d] += c[0] * c[1] * c[2] * find_dp(c[0] - 1, c[1] - 1, c[2] - 1); // 111
// vis[a][b][d] = 1;
return dp[a][b][d];
};
while(q--){
vector<vector<int>> v(3, vector<int>(2 * n));
vector<set<int>> s(3);
for(int j = 0; j < 3; j++){
for(int i = 0; i < 2 * n; i++){
cin >> v[j][i];
s[j].insert(v[j][i]);
}
}
array<int, 3> c = {0, 0, 0};
for(int i = 1; i <= 3 * n; i++){
int ok0 = (s[0].find(i) != s[0].end());
int ok1 = (s[1].find(i) != s[1].end());
int ok2 = (s[2].find(i) != s[2].end());
if(ok0 && ok1)
c[0]++;
if(ok1 && ok2)
c[1]++;
if(ok0 && ok2)
c[2]++;
}
cout << find_dp(c[0], c[1], c[2]) << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Execution timed out |
2093 ms |
860 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2049 ms |
4188 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2070 ms |
55900 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2013 ms |
95572 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2077 ms |
150612 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2095 ms |
223612 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2057 ms |
317008 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2048 ms |
422228 KB |
Time limit exceeded |
