oj.uz

답안 #1106787

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1106787 2024-10-31T04:33:15 Z Math4Life2020 Fishing Game (RMI19_fishing) C++17
100 / 100
 1988 ms 210928 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
//template <class K, class V>
// using ht =
//     gp_hash_table<K, V, hash<K>, equal_to<K>, direct_mask_range_hashing<>,
//                   linear_probe_fn<>,
//                   hash_standard_resize_policy<hash_exponential_size_policy<>,
//                                               hash_load_check_resize_trigger<>, true>>;
using ll = long long; using pii = pair<ll,ll>;
ll N;

const ll p = 1e9+7;
const int pc1 = 255;
unordered_map<int,ll> dp;
inline array<int,3> garr(int x) {
	return (array<int,3>{x>>16,(x>>8)&pc1,x&pc1});
}
inline int gv(array<int,3> a0) {
	return ((a0[0]<<16LL)+(a0[1]<<8LL)+a0[2]);
} 

ll g1Y(int a, int b, int c) { //Y = round already cleared
	if ((a<0)||(b<0)||(c<0)) return 0;
	if ((a+b)==0) {
		return dp[gv({a,b,c})];
	}
	ll v = 0;
	//if (b>=0) {
		v+= b*dp[gv({a,b-1,c})];
	//}
	//if (a>=0) {
		v+= a*dp[gv({a-1,b,c+1})];
	//}
	return (v%p);
}

ll g1N(int a, int b, int c) { //N = round not cleared yet
	if ((a<0)||(b<0)||(c<0)) return 0;
	return (b*dp[gv({a,b-1,c})])%p;
}

ll g2Y(int a, int b, int c) {
	if ((a<0)||(b<0)||(c<0)) return 0;
	if ((a+c)==0) {
		return g1Y(a,b,c);
	}
	ll v = 0;
	v += a*g1Y(a-1,b,c);
	v += c*g1Y(a,b+1,c-1);
	return (v%p);
}

ll g2N(int a, int b, int c) {
	if ((a<0)||(b<0)||(c<0)) return 0;
	//cout << "calling g2N at a,b,c="<<a<<","<<b<<","<<c<<"\n";
	if ((a+c)==0) {
		return g1N(a,b,c);
	}
	ll v = 0;
	v += a*g1Y(a-1,b,c);
	v += c*g1N(a,b+1,c-1);
	return (v%p);
}

ll gdp(int a, int b, int c) {
	if ((a<0)||(b<0)||(c<0)) return 0;
	if ((b+c)==0) {
		return g2N(a,b,c);
	}
	ll v = 0;
	v += c*g2Y(a,b,c-1);
	v += b*g2N(a+1,b-1,c);
	//cout << "gdp at a,b,c="<<a<<","<<b<<","<<c<<"="<<v<<"\n";
	return (v%p);
}

void solve() {
	dp.clear();
	vector<ll> va,vb,vc;
	int prt[3*N];
	for (ll i=0;i<(3*N);i++) {
		prt[i]=0;
	}
	for (int i=0;i<(2*N);i++) {
		int x; cin >> x; x--; //A
		prt[x]^=1;
	}
	for (int i=0;i<(2*N);i++) {
		int x; cin >> x; x--; //B
		prt[x]^=2;
	}
	for (int i=0;i<(2*N);i++) {
		int x; cin >> x; x--; //C
		prt[x]^=4;
	}
	int nea=0,neb=0,nec=0;
	for (int i=0;i<(3*N);i++) {
		if (prt[i]==3) {
			nec++;
		}
		if (prt[i]==5) {
			neb++;
		}
		if (prt[i]==6) {
			nea++;
		}
	}
	ll SM = nea+neb+nec;
	//cout << "nea,neb,nec="<<nea<<","<<neb<<","<<nec<<"\n";
	dp[0]=1;
	for (int S=1;S<=SM;S++) {
		for (int a=0;a<=S;a++) {
			for (int b=0;b<=(S-a);b++) {
				int c = S-a-b;
				dp[gv({a,b,c})]=gdp(a,b,c);
			} 
		}
	}
	cout << dp[gv({nea,neb,nec})] <<"\n";
}

int main() {
	dp.reserve(1LL<<23);
	ll T; 
	cin >> N >> T;
	while(T--) {
		solve();
	}
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 69456 KB Output is correct
2 Correct 21 ms 69468 KB Output is correct
3 Correct 20 ms 69652 KB Output is correct
4 Correct 28 ms 70992 KB Output is correct
5 Correct 263 ms 88620 KB Output is correct
6 Correct 427 ms 102016 KB Output is correct
7 Correct 692 ms 120568 KB Output is correct
8 Correct 992 ms 145232 KB Output is correct
9 Correct 1446 ms 176844 KB Output is correct
10 Correct 1988 ms 210928 KB Output is correct