| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 853222 | 2023-09-23T16:34:20 Z | alexdd | Fishing Game (RMI19_fishing) | C++17 | 417 ms | 218160 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
int dp[305][305][305];
int cardA[205];
int cardB[205];
int cardC[205];
int n;
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
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=1;
int init=dp[ab][bc][ca];
for(int a=0;a<2;a++)
{
if((a==0 && ab==0) || (a==1 && ca==0))
continue;
if(a==0)///scoatem ab
{
prod*=ab;
ab--;
}
else///scoatem ca
{
prod*=ca;
ca--;
bc++;
}
for(int b=0;b<2;b++)
{
if((b==0 && bc==0) || (b==1 && ab==0))
continue;
if(b==0)///scoatem bc
{
prod*=bc;
bc--;
}
else///scoatem ab
{
prod*=ab;
ab--;
ca++;
}
for(int c=0;c<2;c++)
{
if((c==0 && ca==0) || (c==1 && bc==0))
continue;
if(c==0)///scoatem ca
{
prod*=ca;
ca--;
}
else///scoatem bc
{
prod*=bc;
bc--;
ab++;
}
dp[ab][bc][ca]+=(init*prod)%MOD;
dp[ab][bc][ca]%=MOD;
if(c==0)///scoatem ca
{
ca++;
prod*=ca;
}
else///scoatem bc
{
bc++;
ab--;
prod*=bc;
}
}
if(b==0)///scoatem bc
{
bc++;
prod/=bc;
}
else///scoatem ab
{
ab++;
ca--;
prod/=ab;
}
}
if(a==0)///scoatem ab
{
ab++;
prod/=ab;
}
else///scoatem ca
{
ca++;
bc--;
prod/=ca;
}
}
}
}
}
cout<<dp[0][0][0]<<"\n";
}
return 0;
}
/**
dp[ab][bc][ca] = numarul de moduri de a ajunge la o configuratie in care exista ab perechi care au un element in A si celalalt in B
dp[ab-1][bc-1][ca-1] += dp[ab][bc][ca] * ab * bc * ca daca luam din A un ab, luam din B un bc, luam din C un ca
dp[ab-1-1][bc][ca-1+1] += dp[ab][bc][ca] daca luam din A un ab, luam din B un ab, luam din C un ca
*/
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 2 ms | 6488 KB | Output isn't correct |
| 2 | Incorrect | 2 ms | 8540 KB | Output isn't correct |
| 3 | Incorrect | 4 ms | 22876 KB | Output isn't correct |
| 4 | Incorrect | 6 ms | 45656 KB | Output isn't correct |
| 5 | Incorrect | 69 ms | 111452 KB | Output isn't correct |
| 6 | Incorrect | 110 ms | 131960 KB | Output isn't correct |
| 7 | Incorrect | 169 ms | 154460 KB | Output isn't correct |
| 8 | Incorrect | 238 ms | 177108 KB | Output isn't correct |
| 9 | Incorrect | 312 ms | 199516 KB | Output isn't correct |
| 10 | Incorrect | 417 ms | 218160 KB | Output isn't correct |