oj.uz

Submission #260960

# Submission time Handle Problem Language Result Execution time Memory
260960 2020-08-11T08:37:08 Z ryansee Fishing Game (RMI19_fishing) C++14
100 / 100
 340 ms 387580 KB 
#include "bits/stdc++.h"
using namespace std;

#define FAST ios::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x,v) memset(x,v,sizeof(x))
#define siz(x) ll(x.size())
#define all(x) (x).begin(),(x).end()
#define lbd(x,y) (lower_bound(all(x),y)-(x).begin())
#define ubd(x,y) (upper_bound(all(x),y)-(x).begin())
mt19937 rng(123);
long long rand(long long x,long long y){return rng() % (y+1-x) + x; }
string to_string(char c){string s(1,c);return s;}

using ll=long long;
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>;

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (306)
ll n, t, mp[MAXN], memo[202][202][202][3][2], mod=1e9+7;
ll common(vector<ll> x,vector<ll> y){
	mmst(mp,0);
	for(auto i:x) ++mp[i];
	for(auto i:y) ++mp[i];
	ll co = 0; FOR(i,1,3*n) if(mp[i]>1) ++ co;
	return co;
}
ll dp(ll d01,ll d02,ll d12,ll turn,bool gone){
	if(min({d01, d02, d12}) < 0) return 0;
	if(d01==0&&d02==0&&d12==0)return 1;
	if(~memo[d01][d02][d12][turn][gone]) return memo[d01][d02][d12][turn][gone];
	ll&ans=memo[d01][d02][d12][turn][gone]=0;
	if(turn == 0){
		ans=(dp(d01-1, d02, d12, 1, 1) * d01 % mod + dp(d01, d02-1, d12+1, 1, gone) * d02 % mod) % mod;
		if(d01 == 0 && d02 == 0) {
			ans = dp(d01, d02, d12, 1, gone);
		}
	}else if(turn == 1){
		ans=(dp(d01, d02, d12-1, 2, 1) * d12 % mod + dp(d01-1, d02+1, d12, 2, gone) * d01 % mod) % mod;
		if(d01 == 0 && d12 == 0){
			ans=dp(d01, d02, d12, 2, gone);
		}
	}else{
		ans=(dp(d01, d02-1, d12, 0, 0) * d02 % mod + (gone ? dp(d01+1, d02, d12-1, 0, 0) * d12 % mod : 0)) % mod;
		if(d02 == 0 && d12 == 0 && gone){
			ans=dp(d01, d02, d12, 0, gone);
		}
	}
	return ans;
}
int main(){
	mmst(memo,-1);
	FAST
	cin>>n>>t;
	while(t--){
		vector<vector<ll>> A(3, vector<ll>(2*n, 0));
		FOR(j,0,2) FOR(i,0,2*n-1) cin>>A[j][i];
		FOR(j,0,2){
			mmst(mp,0);
			FOR(i,0,2*n-1){
				++ mp[A[j][i]];
			}
			vector<ll> B;
			FOR(i,0,2*n-1) if(mp[A[j][i]]==1) B.eb(A[j][i]);
			A[j]=B;
		}
		cout<<dp(common(A[0], A[1]), common(A[0], A[2]), common(A[1], A[2]), 0, 0)<<'\n';
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 387448 KB Output is correct
2 Correct 192 ms 387448 KB Output is correct
3 Correct 197 ms 387448 KB Output is correct
4 Correct 192 ms 387448 KB Output is correct
5 Correct 209 ms 387452 KB Output is correct
6 Correct 223 ms 387448 KB Output is correct
7 Correct 240 ms 387580 KB Output is correct
8 Correct 269 ms 387448 KB Output is correct
9 Correct 296 ms 387452 KB Output is correct
10 Correct 340 ms 387448 KB Output is correct