답안 #198088

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
198088 2020-01-24T16:21:02 Z model_code Fishing Game (RMI19_fishing) C++17
100 / 100
1131 ms 188508 KB
/**
* 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

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;
      ^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 227 ms 188280 KB Output is correct
2 Correct 294 ms 188268 KB Output is correct
3 Correct 290 ms 188152 KB Output is correct
4 Correct 299 ms 188260 KB Output is correct
5 Correct 541 ms 188300 KB Output is correct
6 Correct 604 ms 188344 KB Output is correct
7 Correct 696 ms 188408 KB Output is correct
8 Correct 798 ms 188508 KB Output is correct
9 Correct 936 ms 188484 KB Output is correct
10 Correct 1131 ms 188380 KB Output is correct