Submission #1062796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062796		Kel_Mahmut	Fishing Game (RMI19_fishing)	C++14	0 / 100	2095 ms	422228 KiB

fishing

#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

int mod = 1e9 + 7;

int main(){
	int n, q;
	cin >> n >> q;
	int N = 3 * n;
	vector<vector<vector<ll>>> dp(N + 1, vector<vector<ll>>(N + 1, vector<ll>(N + 1)));
	vector<vector<vector<ll>>> vis(N + 1, vector<vector<ll>>(N + 1, vector<ll>(N + 1)));
	vis[0][0][0] = 1;
	dp[0][0][0] = 1;
	auto f = [&](vector<int> c, int x, int y, int z) -> pair<ll, vector<int>>{
		if(x == 0 && y == 0 && z == 0) return make_pair(0, c);
		ll coef = 1;
		if(c[0] == 0 || c[1] == 0 || c[2] == 0){
			if(x == 0 && y == 1 && z == 0 && c[0] == 0 && c[1] == 0 && c[2] == 1){
				coef = 1;
				c[2]--;
				return make_pair(coef, c);
			}
			if(x == 0 && y == 1 && z == 0 && c[0] == 0 && c[1] == 0){
				coef = c[2] * (c[2] - 1);
				c[0] = 1;
				c[2] -= 2;
				return make_pair(coef, c);
			}
			if(x == 0 && y == 1 && z == 0 && c[0] == 0 && c[2] == 0){
				coef = 1;
				c[1] -= 1;
				return make_pair(coef, c);
			}
			if(x == 0 && y == 1 && z == 1 && c[0] == 0 && c[2] == 0){
				coef = c[1] * (c[1] - 1);
				c[1] -= 2;
				return make_pair(coef, c);
			}
			if(x == 1 && y == 0 && z == 0 && c[1] == 0 && c[2] == 0 && c[0] == 1){
				c[0]--;
				return make_pair(1, c);
			}
			if(x == 1 && y == 0 && z == 1 && c[1] == 0 && c[2] == 0){
				coef = c[0] * (c[0] - 1);
				c[0] -= 2;
				return make_pair(coef, c);
			}	
			
			return make_pair(0, c);
		}
		if(x == 0){
			coef *= c[1];
			c[1]--;
			c[2]++;
		}
		if(x == 1){
			if(c[0] <= 0) return make_pair(0, c);
			coef *= c[0];
			c[0]--;
		}
		if(y == 0){
			coef *= c[0];
			c[0]--;
			c[1]++;
		}
		if(y == 1){
			if(c[2] <= 0) return make_pair(0, c);
			coef *= c[2];
			c[2]--;
		}
		if(z == 0){
			coef *= c[2];
			c[2]--;
			c[0]++;
		}
		if(z == 1){
			if(c[1] <= 0) return make_pair(0, c);
			coef *= c[1];
			c[1]--;
		}
		return make_pair(coef, c);
	};
	function<ll(int, int, int)> find_dp = [&](int a, int b, int d){
		if(a < 0 || b < 0 || d < 0) return 0ll;
		if(vis[a][b][d]) return dp[a][b][d];
		vector<int> c = {a, b, d};
		for(int x = 0; x < 2; x++) for(int y = 0; y < 2; y++) for(int z = 0; z < 2; z++){
			auto hold = f(c, x, y, z);
			ll coef = hold.first;
			vector<int> tmp = hold.second;
			if(coef != 0) dp[a][b][d] += coef * find_dp(tmp[0], tmp[1], tmp[2]);
		}
		// dp[a][b][d] += c[1] * c[0] * c[1] * find_dp(c[0] - 1, c[1] - 1, c[2] + 1); // 001
		// dp[a][b][d] += c[1] * (c[2] + 1) * (c[2]) * find_dp(c[0] + 1, c[1] - 1, c[2] - 1); // 010
		// dp[a][b][d] += c[1] * (c[2] + 1) * (c[1] - 1) * find_dp(c[0], c[1] - 2, c[2]); // 011
		// dp[a][b][d] += c[0] * (c[0] - 1) * (c[2]) * find_dp(c[0] - 1, c[1] + 1, c[2] - 1); // 100
		// dp[a][b][d] += c[0] * (c[0] - 1) * (c[1] + 1) * find_dp(c[0] - 2, c[1], c[2]); // 101
		// dp[a][b][d] += c[0] * c[2] * (c[2] - 1) * find_dp(c[0], c[1], c[2] - 2); // 110
		// dp[a][b][d] += c[0] * c[1] * c[2] * find_dp(c[0] - 1, c[1] - 1, c[2] - 1); // 111
		// vis[a][b][d] = 1;
		return dp[a][b][d];
	};

	while(q--){
		vector<vector<int>> v(3, vector<int>(2 * n));
		vector<set<int>> s(3);
		for(int j = 0; j < 3; j++){
			for(int i = 0; i < 2 * n; i++){
				cin >> v[j][i];
				s[j].insert(v[j][i]);
			}
		}

		array<int, 3> c = {0, 0, 0};
		for(int i = 1; i <= 3 * n; i++){
			int ok0 = (s[0].find(i) != s[0].end());
			int ok1 = (s[1].find(i) != s[1].end());
			int ok2 = (s[2].find(i) != s[2].end());
			if(ok0 && ok1)
				c[0]++;
			if(ok1 && ok2)
				c[1]++;
			if(ok0 && ok2)
				c[2]++;
		}
		cout << find_dp(c[0], c[1], c[2]) << endl;
	}
}

• Subtask 1: 0 / 100