#include <bits/stdc++.h>
#define DEBUG 1
using namespace std;
namespace output{
void __(short x){cout<<x;}
void __(unsigned x){cout<<x;}
void __(int x){cout<<x;}
void __(long long x){cout<<x;}
void __(unsigned long long x){cout<<x;}
void __(double x){cout<<x;}
void __(long double x){cout<<x;}
void __(char x){cout<<x;}
void __(const char*x){cout<<x;}
void __(const string&x){cout<<x;}
void __(bool x){cout<<(x?"true":"false");}
template<class S,class T>
void __(const pair<S,T>&x){__(DEBUG?"(":""),__(x.first),__(DEBUG?", ":" "),__(x.second),__(DEBUG?")":"");}
template<class T>
void __(const vector<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
template<class T>
void __(const set<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
template<class T>
void __(const multiset<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
template<class S,class T>
void __(const map<S,T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
void pr(){cout<<"\n";}
template<class S,class... T>
void pr(const S&a,const T&...b){__(a);if(sizeof...(b))__(' ');pr(b...);}
}
using namespace output;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef pair<ld,ld> pld;
typedef vector<int> vi;
typedef vector<ll> vl;
#define pb push_back
#define fox(i,x,y) for(int i=(x);i<=(y);i++)
#define foxr(i,x,y) for(int i=(y);i>=(x);i--)
const int MN = 305, mod = 1e9+7;
int dp[MN][MN][MN], N, T, i, j, x, y, w, f, cc[3];
vi pos[MN];
inline void add(int &x,int y){x+=y; if(x>=mod) x-=mod;}
int main(){
for(scanf("%d%d",&N,&T);T;T--){
for(i=1;i<=3*N;i++) pos[i].clear();
for(j=1;j<=3;j++){
for(i=1;i<=2*N;i++){
scanf("%d",&x);
pos[x].pb(j);
}
}
int a=0, b=0, c=0;
for(i=1;i<=3*N;i++){
if(pos[i][0]==pos[i][1]) continue;
pii p(pos[i][0],pos[i][1]);
if(p.first>p.second) swap(p.first,p.second);
if(p==make_pair(2,3)) a++;
else if(p==make_pair(1,3)) b++;
else c++;
}
dp[0][0][0]=1;
int tt;
if(N>=90) tt = ceil(1.0/3.0*(a+b+c));
else tt = a+b+c;
for(int s=1;s<=a+b+c;s++){
for(i=0;i<=min(s,a+tt);i++){
for(j=0;j<=min(s,b+tt);j++){
int k = s-i-j;
if(k<0||k>min(s,c+tt)) continue;
dp[i][j][k] = 0;
for(int ii=0;ii<3;ii++){
if(ii==2&&j+k) continue;
for(int jj=0;jj<3;jj++){
for(int kk=0;kk<3;kk++){
cc[0]=k,cc[1]=i,cc[2]=j; f=1;
if(ii!=2){
if(ii==0&&cc[0]>0) f=1LL*f*cc[0]%mod,cc[0]--;
else if(ii==1&&cc[2]>0) f=1LL*f*cc[2]%mod, cc[2]--,cc[1]++;
else continue;
}
if(jj!=2||cc[0]+cc[1]>0){
if(jj==0&&cc[1]>0) f=1LL*f*cc[1]%mod,cc[1]--;
else if(jj==1&&cc[0]>0) f=1LL*f*cc[0]%mod,cc[0]--,cc[2]++;
else continue;
}
if(kk!=2||cc[1]+cc[2]>0){
if(kk==0&&cc[2]>0) f=1LL*f*cc[2]%mod,cc[2]--;
else if(kk==1&&cc[1]>0) f=1LL*f*cc[1]%mod,cc[1]--,cc[0]++;
else continue;
}
if(cc[0]+cc[1]+cc[2]<i+j+k) dp[i][j][k]=(dp[i][j][k]+1LL*f*dp[cc[1]][cc[2]][cc[0]])%mod;
}
}
}
}
}
}
printf("%d\n",dp[a][b][c]);
}
return 0;
}
Compilation message
fishing.cpp: In function 'int main()':
fishing.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(scanf("%d%d",&N,&T);T;T--){
~~~~~^~~~~~~~~~~~~~
fishing.cpp:57:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
380 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
15 ms |
2812 KB |
Output is correct |
| 5 |
Correct |
269 ms |
14584 KB |
Output is correct |
| 6 |
Correct |
506 ms |
20692 KB |
Output is correct |
| 7 |
Correct |
860 ms |
27896 KB |
Output is correct |
| 8 |
Correct |
1206 ms |
35892 KB |
Output is correct |
| 9 |
Correct |
1474 ms |
35320 KB |
Output is correct |
| 10 |
Execution timed out |
2067 ms |
42488 KB |
Time limit exceeded |
