oj.uz

Submission #259623

# Submission time Handle Problem Language Result Execution time Memory
259623 2020-08-08T05:23:13 Z oolimry Fishing Game (RMI19_fishing) C++14
100 / 100
 164 ms 157048 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
using namespace std;
typedef pair<int,int> ii;
typedef long long lint;

const int mod = 1000000007;

void fix(lint &x){
	x %= mod;
	if(x < 0) x += mod;
}

const int Aturn = 0;
const int Btake = 1;
const int Bnotake = 2;
const int Ctake = 3;
const int Cnotake = 4; 

int memo[5][200][200][200];

lint dp(int type, lint AB, lint BC, lint AC){
	
	if(AB == 0 && BC == 0 && AC == 0) return 1;
	if(AB < 0 || BC < 0 || AC < 0) return 0;
	if(memo[type][AB][BC][AC] != -1) return memo[type][AB][BC][AC];
	
	lint A = AB+AC, B = BC+AB, C = AC+BC;
	lint ans = 0;
	
	if(type == Aturn){
		ans = AB * dp(Btake, AB-1, BC, AC) + AC * dp(Bnotake, AB, BC+1, AC-1);
		if(A == 0) ans = dp(Bnotake, AB, BC, AC);
	}
	else if(type == Btake){
		ans = BC * dp(Ctake, AB, BC-1, AC) + AB * dp(Ctake, AB-1, BC, AC+1); 
		if(B == 0) ans = dp(Ctake, AB, BC, AC);
	}
	else if(type == Bnotake){
		ans = BC * dp(Ctake, AB, BC-1, AC) + AB * dp(Cnotake, AB-1, BC, AC+1); 
		if(B == 0) ans = dp(Cnotake, AB, BC, AC);
	}
	else if(type == Ctake){
		ans = AC * dp(Aturn, AB, BC, AC-1) + BC * dp(Aturn, AB+1, BC-1, AC);
		if(C == 0) ans = dp(Aturn, AB, BC, AC);
	}
	else{
		ans = AC * dp(Aturn, AB, BC, AC-1);
	}
	
	fix(ans);
	memo[type][AB][BC][AC] = ans;
	//cout << type << " " << AB << " " << BC << " " << AC << " " << ans << endl;
	return ans;
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	memset(memo, -1, sizeof(memo));
	
	int n, TC; cin >> n >>TC;
	while(TC--){
		
		ii cnt[3*n+4]; fill(cnt,cnt+3*n+4,ii(0,0));
		
		for(int k = 1;k <= 3;k++){
			for(int i = 0;i < 2*n;i++){
				int a; cin >> a;
				if(cnt[a].first == 0) cnt[a].first = k;
				else cnt[a].second = k;
			}
		}
		
		int AB = 0, BC = 0, AC = 0;
		
		for(int i = 1;i <= 3*n;i++){
			int f = cnt[i].first, s = cnt[i].second;
			//cout << f << " " << s << endl;
			if(f == s) continue;
			if(f == 1 && s == 2) AB++;
			if(f == 1 && s == 3) AC++;
			if(f == 2 && s == 3) BC++;
		}
		
		//cout << AB << " " << BC << " " << AC << "\n";
		cout << dp(Aturn, AB, BC, AC) << "\n";
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 156920 KB Output is correct
2 Correct 78 ms 156920 KB Output is correct
3 Correct 78 ms 156920 KB Output is correct
4 Correct 80 ms 156888 KB Output is correct
5 Correct 93 ms 156920 KB Output is correct
6 Correct 96 ms 156920 KB Output is correct
7 Correct 106 ms 156920 KB Output is correct
8 Correct 121 ms 156920 KB Output is correct
9 Correct 142 ms 157048 KB Output is correct
10 Correct 164 ms 156920 KB Output is correct