#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
ll N;
const ll p = 1e9+7;
const int pc1 = 255;
map<int,ll> dp;
inline array<int,3> garr(int x) {
return (array<int,3>{x>>16,(x>>8)&pc1,x&pc1});
}
inline int gv(array<int,3> a0) {
return ((a0[0]<<16LL)+(a0[1]<<8LL)+a0[2]);
}
ll g1Y(int a, int b, int c) { //Y = round already cleared
if ((a<0)||(b<0)||(c<0)) return 0;
ll v = 0;
//if (b>=0) {
v+= b*dp[gv({a,b-1,c})];
//}
//if (a>=0) {
v+= a*dp[gv({a-1,b,c+1})];
//}
return (v%p);
}
ll g1N(int a, int b, int c) { //N = round not cleared yet
if ((a<0)||(b<0)||(c<0)) return 0;
return (b*dp[gv({a,b-1,c})])%p;
}
ll g2Y(int a, int b, int c) {
if ((a<0)||(b<0)||(c<0)) return 0;
ll v = 0;
v += a*g1Y(a-1,b,c);
v += c*g1Y(a,b+1,c-1);
return (v%p);
}
ll g2N(int a, int b, int c) {
if ((a<0)||(b<0)||(c<0)) return 0;
cout << "calling g2N at a,b,c="<<a<<","<<b<<","<<c<<"\n";
ll v = 0;
v += a*g1Y(a-1,b,c);
v += c*g1N(a,b+1,c-1);
return (v%p);
}
ll gdp(int a, int b, int c) {
if ((a<0)||(b<0)||(c<0)) return 0;
ll v = 0;
v += c*g2Y(a,b,c-1);
v += b*g2N(a+1,b-1,c);
return (v%p);
}
void solve() {
dp.clear();
vector<ll> va,vb,vc;
int prt[3*N];
for (ll i=0;i<(3*N);i++) {
prt[i]=0;
}
for (int i=0;i<(2*N);i++) {
int x; cin >> x; x--; //A
prt[x]|=1;
}
for (int i=0;i<(2*N);i++) {
int x; cin >> x; x--; //B
prt[x]|=2;
}
for (int i=0;i<(2*N);i++) {
int x; cin >> x; x--; //C
prt[x]|=4;
}
int nea=0,neb=0,nec=0;
for (int i=0;i<(3*N);i++) {
if (prt[i]==3) {
nec++;
}
if (prt[i]==5) {
neb++;
}
if (prt[i]==6) {
nea++;
}
}
ll SM = nea+neb+nec;
//cout << "nea,neb,nec="<<nea<<","<<neb<<","<<nec<<"\n";
dp[0]=1;
for (int S=1;S<=SM;S++) {
for (int a=0;a<=S;a++) {
for (int b=0;b<=(S-a);b++) {
for (int c=0;c<=(S-a-b);c++) {
if (a==0 && b==0 && c==0) {
continue;
}
//cout << "processing "
dp[gv({a,b,c})]=gdp(a,b,c);
}
}
}
}
cout << dp[gv({nea,neb,nec})];
}
int main() {
ll T;
cin >> N >> T;
while(T--) {
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Incorrect |
46 ms |
3064 KB |
Output isn't correct |
| 4 |
Incorrect |
656 ms |
30820 KB |
Output isn't correct |
| 5 |
Execution timed out |
2067 ms |
106292 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2068 ms |
96944 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2077 ms |
101528 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2055 ms |
105944 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2065 ms |
107900 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2051 ms |
101556 KB |
Time limit exceeded |
