oj.uz

답안 #366566

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
366566 2021-02-14T14:12:31 Z MladenP Fishing Game (RMI19_fishing) C++17
100 / 100
 387 ms 435436 KB 
/**
* 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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 273 ms 435308 KB Output is correct
2 Correct 254 ms 435328 KB Output is correct
3 Correct 247 ms 435308 KB Output is correct
4 Correct 242 ms 435436 KB Output is correct
5 Correct 278 ms 435308 KB Output is correct
6 Correct 283 ms 435308 KB Output is correct
7 Correct 282 ms 435308 KB Output is correct
8 Correct 330 ms 435420 KB Output is correct
9 Correct 338 ms 435308 KB Output is correct
10 Correct 387 ms 435308 KB Output is correct