Submission #568516

#	Time	Username	Problem	Language	Result	Execution time	Memory
568516		urosk	Fishing Game (RMI19_fishing)	C++14	0 / 100	297 ms	147468 KiB

fishing

// __builtin_popcount(x)
// __builtin_popcountll(x)
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;

#define maxn 105
#define maxx 1005
#define mod 1000000007
ll n;
ll a[3*maxn];
ll b[3*maxn];
ll c[3*maxn];
ll dp[maxn][maxn][maxn][4][2];
ll fact[3*maxn];
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
ll reshi(ll ab,ll bc,ll ca,ll muv,bool bio){
    if(ab+bc==0||bc+ca==0||ca+ab==0) return fact[max({ab,bc,ca})];
    if(dp[ab][bc][ca][muv][bio]!=-1) return dp[ab][bc][ca][muv][bio];
    ll ans = 0;
    if(muv==1){
        if(ab) ans = add(ans,mul(ab,reshi(ab-1,bc,ca,2,1)));
        if(ca) ans = add(ans,mul(ca,reshi(ab,bc+1,ca-1,2,bio)));
    }else if(muv==2){
        if(bc) ans = add(ans,mul(bc,reshi(ab,bc-1,ca,3,1)));
        if(ab) ans = add(ans,mul(ca,reshi(ab-1,bc,ca+1,3,bio)));
    }else{
        if(ca) ans = add(ans,mul(ca,reshi(ab,bc,ca-1,1,0)));
        if(bio){
            if(bc) ans = add(ans,mul(bc,reshi(ab+1,bc-1,ca,1,0)));
        }
    }
    return dp[ab][bc][ca][muv][bio] = ans;
}
void tc(){
    for(ll i = 0;i<maxn;i++) for(ll j = 0;j<maxn;j++) for(ll k = 0;k<maxn;k++) for(ll e = 0;e<4;e++) for(ll r = 0;r<2;r++) dp[i][j][k][e][r] = -1;
	for(ll i = 1;i<=3*n;i++) a[i] = b[i] = c[i] = 0;
	for(ll i = 1;i<=2*n;i++){
		ll x; cin >> x;
		a[x]++;
		if(a[x]==2) a[x] = 0;
	}
	for(ll i = 1;i<=2*n;i++){
		ll x; cin >> x;
		b[x]++;
		if(b[x]==2) b[x] = 0;
	}
	for(ll i = 1;i<=2*n;i++){
		ll x; cin >> x;
		c[x]++;
		if(c[x]==2) c[x] = 0;
	}
	ll ab = 0,bc = 0,ca = 0;
	for(ll i = 1;i<=3*n;i++){
		if(a[i]&&b[i]) ab++;
		if(c[i]&&b[i]) bc++;
		if(a[i]&&c[i]) ca++;
	}
	ll cnta = 0,cntb = 0,cntc = 0;
	for(ll i = 1;i<=3*n;i++) cnta+=a[i];
	for(ll i = 1;i<=3*n;i++) cntb+=b[i];
	for(ll i = 1;i<=3*n;i++) cntc+=c[i];
	if(cnta>0) cout<<reshi(ab,bc,ca,1,0)<<endl;
	else cout<<reshi(ab,bc,ca,2,0)<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
	fact[0] = 1;
	for(ll i = 1;i<3*maxn;i++) fact[i] = mul(fact[i-1],i);
	int t; cin >> n >> t;
	while(t--) tc();
	return 0;
}

• Subtask 1: 0 / 100