oj.uz

Submission #259646

# Submission time Handle Problem Language Result Execution time Memory
259646 2020-08-08T06:24:32 Z lyc Fishing Game (RMI19_fishing) C++14
100 / 100
 346 ms 467832 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ll=long long;

const int mxN = 100;
const int mod = 1e9+7;

int N, T, A[2*mxN], B[2*mxN], C[2*mxN];

int fac[3*mxN], AB, BC, AC;
int res[271][271][271][3][2];
int dp(int ab, int bc, int ac, int p, int f) {
	if (ab == 0 && bc == 0) return fac[ac];
	if (ab == 0 && ac == 0) return fac[bc];
	if (bc == 0 && ac == 0) return fac[ab];
	//~ TRACE(ab _ bc _ ac _ p _ f);
	int& ans = res[ab][bc][ac][p][f];
	if (~ans) return ans;
	
	ans = 0;
	if (p == 0) {
		if (ab) ans += (ll) ab * dp(ab-1, bc, ac, p+1, 1) % mod;
		if (ac) ans += (ll) ac * dp(ab, bc+1, ac-1, p+1, f) % mod;
		if (!ab && !ac) ans += (ll) dp(ab, bc, ac, p+1, f) % mod;
		ans %= mod;
	} else if (p == 1) {
		if (bc) ans += (ll) bc * dp(ab, bc-1, ac, p+1, 1) % mod;
		if (ab) ans += (ll) ab * dp(ab-1, bc, ac+1, p+1, f) % mod;
		if (!ab && !ac) ans += (ll) dp(ab, bc, ac, p+1, f) % mod;
		ans %= mod;
	} else if (p == 2) {
		if (ac) ans += (ll) ac * dp(ab, bc, ac-1, 0, 0) % mod;
		if (f) {
			if (bc) ans += (ll) bc * dp(ab+1, bc-1, ac, 0, 0) % mod;
			if (!ab && !ac) ans += (ll) dp(ab, bc, ac, 0, 0) % mod;
			ans %= mod;
		}
	}
	//~ TRACE(ab _ bc _ ac _ p _ f _ "::" _ ans);
	return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N >> T;
    
    fac[0] = 1;
    FOR(i,1,3*N) fac[i] = (ll) fac[i-1] * i % mod;
    memset(res,-1,sizeof res);
    
    while (T--) {
		FOR(i,1,2*N){ cin >> A[i]; }
		FOR(i,1,2*N){ cin >> B[i]; }
		FOR(i,1,2*N){ cin >> C[i]; }
		
		AB = BC = AC = 0;
		FOR(i,1,2*N) FOR(j,1,2*N) if (A[i] == B[j]) ++AB;
		FOR(i,1,2*N) FOR(j,1,2*N) if (B[i] == C[j]) ++BC;
		FOR(i,1,2*N) FOR(j,1,2*N) if (A[i] == C[j]) ++AC;
		
		//~ TRACE(AB _ BC _ AC);
		cout << dp(AB,BC,AC,0,0) << '\n';
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 467704 KB Output is correct
2 Correct 230 ms 467704 KB Output is correct
3 Correct 220 ms 467704 KB Output is correct
4 Correct 222 ms 467680 KB Output is correct
5 Correct 238 ms 467708 KB Output is correct
6 Correct 244 ms 467832 KB Output is correct
7 Correct 260 ms 467832 KB Output is correct
8 Correct 279 ms 467704 KB Output is correct
9 Correct 307 ms 467772 KB Output is correct
10 Correct 346 ms 467704 KB Output is correct