Submission #366566

#	Time	Username	Problem	Language	Result	Execution time	Memory
366566		MladenP	Fishing Game (RMI19_fishing)	C++17	100 / 100	387 ms	435436 KiB

fishing

/**
* user:  puzic-97a
* fname: Mladen
* lname: Puzic
* task:  fishing
* score: 100.0
* date:  2019-10-11 07:39:11.906428
*/
#include <bits/stdc++.h>
#define PRINT(x) cerr<<#x<<'='<<x<<endl
#define NL(x) " \n"[(x)]
#define sz(x) int((x).size())
#define all(x) begin(x),end(x)
#define mid (l+r)/2
#define fi first
#define se second
#define pb push_back
#define endl '\n'
#define lld long long
#define pii pair<int,int>
#define pli pair<lld,int> 
#define pil pair<int,lld>
#define pll pair<lld,lld>
#define INF 1000000000
#define LINF 1000000000000000000LL
#define EPS 1e-9
using namespace std;
#define MOD 1000000007
#define MAXN 210
lld dp[MAXN][MAXN][MAXN][3][2];
int N, T;
set<int> A, B, C;
lld bt(lld AB, lld BC, lld CA, int k, int t) {
	/*PRINT(AB);
	PRINT(BC);
	PRINT(CA);
	PRINT(k);
	PRINT(t);*/
	if(dp[AB][BC][CA][k][t] != -1) return dp[AB][BC][CA][k][t];
	dp[AB][BC][CA][k][t] = 0;
	if(k == 0) {
		if(AB > 0) dp[AB][BC][CA][k][t] += AB*bt(AB-1, BC, CA, 1, 1);
		if(CA > 0) dp[AB][BC][CA][k][t] += CA*bt(AB, BC+1, CA-1, 1, t);
		if(AB == 0 && CA == 0) dp[AB][BC][CA][k][t] += bt(AB, BC, CA, 1, t);
	} else if(k == 1) {
		if(BC > 0) dp[AB][BC][CA][k][t] += BC*bt(AB, BC-1, CA, 2, 1);
		if(AB > 0) dp[AB][BC][CA][k][t] += AB*bt(AB-1, BC, CA+1, 2, t);
		if(BC == 0 && AB == 0) dp[AB][BC][CA][k][t] += bt(AB, BC, CA, 2, t);
	} else if(k == 2) {
		if(t == 0 && CA == 0) return 0;
		if(CA > 0) dp[AB][BC][CA][k][t] += CA*bt(AB, BC, CA-1, 0, 0);
		if(t == 1 && BC > 0) dp[AB][BC][CA][k][t] += BC*bt(AB+1, BC-1, CA, 0, 0);
		if(CA == 0 && BC == 0) dp[AB][BC][CA][k][t] += bt(AB, BC, CA, 0, 0);
	}
	if(dp[AB][BC][CA][k][t] >= MOD) dp[AB][BC][CA][k][t] %= MOD;
	return dp[AB][BC][CA][k][t];
}
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0);
	for(int i = 0; i < MAXN; i++) {
		for(int j = 0; j < MAXN; j++) {
			for(int k = 0; k < MAXN; k++) dp[i][j][k][0][0] = dp[i][j][k][1][0] = dp[i][j][k][2][0] = dp[i][j][k][0][1] = dp[i][j][k][1][1] = dp[i][j][k][2][1] = -1;
		}
	}
	dp[0][0][0][0][0] = 1;
	cin >> N >> T;
	while(T--) {
		A.clear(); B.clear(); C.clear();
		lld AB = 0, BC = 0, CA = 0;
		for(int i = 0; i < 2*N; i++) {
			int x; cin >> x;
			if(A.find(x) != A.end()) A.erase(x);
			else A.insert(x);
		}
		for(int i = 0; i < 2*N; i++) {
			int x; cin >> x;
			if(B.find(x) != B.end()) B.erase(x);
			else B.insert(x);
		}
		for(int i = 0; i < 2*N; i++) {
			int x; cin >> x;
			if(C.find(x) != C.end()) C.erase(x);
			else C.insert(x);
		}
		for(auto x : A) {
			if(B.find(x) != B.end()) AB++;
			if(C.find(x) != C.end()) CA++;
		}
		for(auto x : B) {
			if(C.find(x) != C.end()) BC++;
		}
		cout << bt(AB, BC, CA, 0, 0) << endl;
	}
	return 0;
}
/*
1 5
1 2
2 3
3 1
1 1 
2 3
3 2
1 1 
2 2
3 3
1 3
2 2
3 1
1 2
2 1
3 3

1 1
1 1 
2 3 
3 2
*/

• Subtask 1: 100 / 100