oj.uz

Submission #342015

# Submission time Handle Problem Language Result Execution time Memory
342015 2021-01-01T03:47:35 Z Gajowy Fishing Game (RMI19_fishing) C++14
100 / 100
 1061 ms 59372 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int MAXN=3e2+10;
const int mod=1e9+7;

int dp[MAXN][MAXN][MAXN];
bool isa[MAXN],isb[MAXN],isc[MAXN];

void add(int &x,int v){
	x+=v;
	if(x>=mod)
		x-=mod;
}

int mul(ll x,ll y){
	return (x*y)%mod;
}

int sum(int x,int y){
	return (x+y>=mod?x+y-mod:x+y);
}

void sub(int &x,int v){
	x-=v;
	if(x<0)
		x+=mod;
}

void prep(){
	dp[0][0][0]=1;
	int va,vb,vc,pos;
	for(int s=0;s<MAXN-4;s++){
		for(int a=0;a<=s;a++){
			for(int b=0;a+b<=s;b++){
				int c=s-a-b;
					for(int aa=0;aa<3;aa++){
						for(int bb=0;bb<3;bb++){
							for(int cc=0;cc<3;cc++){
								va=a,vb=b,vc=c;
								pos=dp[a][b][c];
								
								if(cc==0){
									if(vc!=0||vb!=0)
										continue;
								}
								else
								if(cc==1){
									if(va==0)
										continue;
									va--;
									vb++;
									pos=mul(pos,vb);
								}
								else
								{
									vc++;
									pos=mul(pos,vc);
								}

								if(bb==0){
									if(vb!=0||va!=0)
										continue;
								}
								else
								if(bb==1){
									if(vc==0)
										continue;
									vc--;
									va++;
									pos=mul(pos,va);
								}
								else{
									vb++;
									pos=mul(pos,vb);
								}

								if(aa==0){
									if(va!=0||vc!=0)
										continue;
								}
								else
								if(aa==1){
									if(vb==0)
										continue;
									vb--;
									vc++;
									pos=mul(pos,vc);
								}
								else{
									va++;
									pos=mul(pos,va);
								}
								
								if(va+vb+vc==s)
									continue;
								//if(va==0&&vb==0&&vc==1)
									//cout<<a<<' '<<b<<' '<<c<<'\n';
								add(dp[va][vb][vc],pos);
							}
						}
					}
				
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,t;
	prep();
	cin>>n>>t;
	while(t--){
		for(int i=1;i<=3*n;i++)
			isa[i]=isb[i]=isc[i]=false;
		for(int i=1;i<=2*n;i++){
			int x;
			cin>>x;
			isa[x]=true;
		}
		for(int i=1;i<=2*n;i++){
			int x;
			cin>>x;
			isb[x]=true;
		}
		for(int i=1;i<=2*n;i++){
			int x;
			cin>>x;
			isc[x]=true;
		}
		int a=0,b=0,c=0;
		for(int i=1;i<=3*n;i++){
			if(isa[i]&&isb[i])
				a++;
			else
			if(isb[i]&&isc[i])
				b++;
			else
			if(isc[i]&&isa[i])
				c++;
		}
		cout<<dp[a][b][c]<<'\n';
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1006 ms 59116 KB Output is correct
2 Correct 1022 ms 59164 KB Output is correct
3 Correct 1029 ms 59216 KB Output is correct
4 Correct 1042 ms 59116 KB Output is correct
5 Correct 1022 ms 59116 KB Output is correct
6 Correct 1036 ms 59244 KB Output is correct
7 Correct 1026 ms 59372 KB Output is correct
8 Correct 1048 ms 59132 KB Output is correct
9 Correct 1032 ms 59116 KB Output is correct
10 Correct 1061 ms 59244 KB Output is correct