Submission #198088

#	Time	Username	Problem	Language	Result	Execution time	Memory
198088		model_code	Fishing Game (RMI19_fishing)	C++17	100 / 100	1131 ms	188508 KiB

fishing

/**
* user:  frolov-001
* fname: Konstantin
* lname: Frolov
* task:  fishing
* score: 100.0
* date:  2019-10-11 08:36:38.611566
*/
#include <bits/stdc++.h>
#define FOR(i, n) for (int i = 0; i < n; ++i)
#define debug(x) std::cout << #x << ": " << x << '\n';
#define pb push_back
typedef long long ll;
const int N = 200, MOD = 1e9 + 7;
int dp[N][N][N][3][2];
void add(int &x, int y) {
	x += y;
	if (x >= MOD) x -= MOD;
}
int mult(int a, int b) {
	return (a * 1LL * b) % MOD;
}
void reCount(int AB, int BC, int AC, int turn, int has) {
	if (dp[AB][BC][AC][turn][has] != -1) return;
	dp[AB][BC][AC][turn][has] = 0;
	int all = (AB + BC + AC) * 2;
	int m[] = {AB, BC, AC};
	int other1 = (turn + 1) % 3, other2 = (turn + 2) % 3;
	int hasEmptyTurn = (m[other2] != 0);
	// debug(AB << ' ' << BC << ' ' << AC << ' ' << turn << ' ' << has)
	// debug(hasEmptyTurn)
	if (!hasEmptyTurn && m[turn] == 0) {
		if (turn == 2) {
			if (!has) return;
			reCount(m[0], m[1], m[2], 0, 0);
			add(dp[AB][BC][AC][turn][has], dp[m[0]][m[1]][m[2]][0][0]);
		}
		else {
			reCount(m[0], m[1], m[2], turn + 1, has);
			add(dp[AB][BC][AC][turn][has], dp[m[0]][m[1]][m[2]][turn + 1][has]);
		}
	}
	if (hasEmptyTurn) {
		m[other1]++;
		m[other2]--;
		if (turn == 2 && has) {
			reCount(m[0], m[1], m[2], 0, 0);
			add(dp[AB][BC][AC][turn][has], mult(dp[m[0]][m[1]][m[2]][0][0], m[other2] + 1));
		}
		else if (turn != 2) {
			reCount(m[0], m[1], m[2], turn + 1, has);
			// debug
			// debug(m[other2] + 1 << ' ' << turn << ' ' << AB << ' ' << BC << ' ' << AC)
			add(dp[AB][BC][AC][turn][has], mult(dp[m[0]][m[1]][m[2]][turn + 1][has], m[other2] + 1));
		}
		m[other1]--;
		m[other2]++;
	}
	if (m[turn] != 0) {
		m[turn]--;
		if (turn == 2) {
			reCount(m[0], m[1], m[2], 0, 0);
			// reCount(dp[m[0]][m[1]][m[2]][0][0]);
			add(dp[AB][BC][AC][turn][has], mult(dp[m[0]][m[1]][m[2]][0][0], m[turn] + 1));
		
			// add(dp[m[0]][m[1]][m[2]][(turn + 1) % 3][1], mult(dp[AB][BC][AC][turn][has], (m[turn] + 1)));
		}
		else {
			reCount(m[0], m[1], m[2], turn + 1, 1);
			// reCount(dp[m[0]][m[1]][m[2]][turn + 1][1]);
			add(dp[AB][BC][AC][turn][has], mult(dp[m[0]][m[1]][m[2]][turn + 1][1], m[turn] + 1));
		}
	}
}
int inter(std::set<int> &a, std::set<int> &b) {
	int cnt = 0;
	for (auto e : a) cnt += b.count(e);
	return cnt;
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0); std::cout.tie(0);
	int t, n;
	std::cin >> n >> t;
	while (t--) {
		memset(dp, -1, sizeof(dp));
		std::set<int> A, B, C;
		FOR(i, 2 * n) {
			int x;
			std::cin >> x;
			if (A.count(x)) {
				A.erase(x);
			}
			else {
				A.insert(x);
			}
		}
		FOR(i, 2 * n) {
			int x;
			std::cin >> x;
			if (B.count(x)) {
				B.erase(x);
			}
			else {
				B.insert(x);
			}
		}
		FOR(i, 2 * n) {
			int x;
			std::cin >> x;
			if (C.count(x)) {
				C.erase(x);
			}
			else {
				C.insert(x);
			}
		}
		FOR(j, 3) {
			FOR(q, 2) {
				dp[0][0][0][j][q] = 1;
			}
		}
		reCount(inter(A, B), inter(B, C), inter(A, C), 0, 0);
		std::cout << dp[inter(A, B)][inter(B, C)][inter(A, C)][0][0] << '\n';
	}
}

Compilation message (stderr)

fishing.cpp: In function 'void reCount(int, int, int, int, int)':
fishing.cpp:26:6: warning: unused variable 'all' [-Wunused-variable]
  int all = (AB + BC + AC) * 2;
      ^~~

• Subtask 1: 100 / 100