| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 853247 | 2023-09-23T18:19:58 Z | alexdd | Fishing Game (RMI19_fishing) | C++17 | 486 ms | 218128 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
int put(int a, int exp)
{
if(exp==0)
return 1;
if(exp%2==0)
return put((a*a)%MOD,exp/2);
else
return (put((a*a)%MOD,exp/2)*a)%MOD;
}
int dp[305][305][305];
int cardA[205];
int cardB[205];
int cardC[205];
int inv[305];
int n;
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
for(int i=0;i<=300;i++)
inv[i]=put(i,MOD-2);
int t;
cin>>n>>t;
while(t--)
{
for(int i=1;i<=2*n;i++)
cin>>cardA[i];
for(int i=1;i<=2*n;i++)
cin>>cardB[i];
for(int i=1;i<=2*n;i++)
cin>>cardC[i];
int cntab=0,cntbc=0,cntca=0;
for(int i=1;i<=2*n;i++)
{
for(int j=1;j<=2*n;j++)
{
if(cardA[i]==cardB[j])
cntab++;
if(cardB[i]==cardC[j])
cntbc++;
if(cardC[i]==cardA[j])
cntca++;
}
}
for(int i=0;i<=3*n;i++)
for(int j=0;j<=3*n;j++)
for(int k=0;k<=3*n;k++)
dp[i][j][k]=0;
dp[cntab][cntbc][cntca]=1;
for(int tot=cntab+cntbc+cntca;tot>0;tot--)
{
for(int ab=0;ab<=tot;ab++)
{
for(int bc=0;bc+ab<=tot;bc++)
{
int ca = tot-ab-bc;
if(dp[ab][bc][ca]==0)
continue;
int prod=dp[ab][bc][ca];
int initab=ab,initbc=bc,initca=ca;
for(int a=0;a<2;a++)
{
if(((a==0 && ab==0 && ab+ca>0) || (a==1 && ca==0)))
continue;
bool difa=0;
if(ab+ca>0)
difa=1;
if(a==0)///scoatem ab
{
if(difa)
{
prod*=ab;
prod%=MOD;
ab--;
}
}
else///scoatem ca
{
prod*=ca;
prod%=MOD;
ca--;
bc++;
}
for(int b=0;b<2;b++)
{
if((b==0 && bc==0 && bc+ab>0) || (b==1 && ab==0))
continue;
bool difb=0;
if(bc+ab>0)
difb=1;
if(b==0)///scoatem bc
{
if(difa)
{
prod*=bc;
prod%=MOD;
bc--;
}
}
else///scoatem ab
{
prod*=ab;
prod%=MOD;
ab--;
ca++;
}
for(int c=0;c<2;c++)
{
if((c==0 && ca==0 && ca+bc>0) || (c==1 && bc==0))
continue;
bool difc=0;
if(ca+bc>0)
difc=1;
if(c==0)///scoatem ca
{
if(difc)
{
prod*=ca;
prod%=MOD;
ca--;
}
}
else///scoatem bc
{
prod*=bc;
prod%=MOD;
bc--;
ab++;
}
if(ab!=initab || bc!=initbc || ca!=initca)
{
dp[ab][bc][ca]+=prod;
dp[ab][bc][ca]%=MOD;
}
if(c==0)///scoatem ca
{
if(difc)
{
ca++;
prod*=inv[ca];
prod%=MOD;
}
}
else///scoatem bc
{
bc++;
ab--;
prod*=inv[bc];
prod%=MOD;
}
}
if(b==0)///scoatem bc
{
if(difb)
{
bc++;
prod*=inv[bc];
prod%=MOD;
}
}
else///scoatem ab
{
ab++;
ca--;
prod*=inv[ab];
prod%=MOD;
}
}
if(a==0)///scoatem ab
{
if(difa)
{
ab++;
prod*=inv[ab];
prod%=MOD;
}
}
else///scoatem ca
{
ca++;
bc--;
prod*=inv[ca];
prod%=MOD;
}
}
}
}
}
cout<<dp[0][0][0]<<"\n";
}
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 6492 KB | Output is correct |
| 2 | Correct | 1 ms | 8620 KB | Output is correct |
| 3 | Correct | 3 ms | 22872 KB | Output is correct |
| 4 | Correct | 7 ms | 45660 KB | Output is correct |
| 5 | Correct | 95 ms | 111196 KB | Output is correct |
| 6 | Correct | 132 ms | 131948 KB | Output is correct |
| 7 | Correct | 194 ms | 154456 KB | Output is correct |
| 8 | Correct | 282 ms | 177052 KB | Output is correct |
| 9 | Correct | 379 ms | 199672 KB | Output is correct |
| 10 | Correct | 486 ms | 218128 KB | Output is correct |