| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 291810 | 2020-09-05T19:52:40 Z | nicolaalexandra | Fishing Game (RMI19_fishing) | C++14 | 564 ms | 117112 KB |
#include <bits/stdc++.h>
#define DIM 310
#define MOD 1000000007
using namespace std;
int dp[DIM][DIM][DIM],fa[DIM*2],fb[DIM*2],fc[DIM*3],a[DIM],b[DIM],c[DIM];
int t,n,i,j,k;
int main (){
//ifstream cin ("fishing.in");
//ofstream cout ("fishing.out");
cin>>n>>t;
for (;t--;){
memset (fa,0,sizeof fa);
memset (fb,0,sizeof fb);
memset (fc,0,sizeof fc);
for (i=1;i<=2*n;i++){
cin>>a[i];
fa[a[i]]++;
}
for (i=1;i<=2*n;i++){
cin>>b[i];
fb[b[i]]++;
}
for (i=1;i<=2*n;i++){
cin>>c[i];
fc[c[i]]++;
}
int nr_ab = 0, nr_ac = 0, nr_bc = 0;
for (i=1;i<=3*n;i++){
if (fa[i] && fb[i]) /// cate au in comun a si b
nr_ab++;
if (fa[i] && fc[i]) /// cate au in comun a si c
nr_ac++;
if (fb[i] && fc[i]) /// cate au in comun b si c
nr_bc++;
}
memset (dp,0,sizeof dp);
dp[nr_ab][nr_ac][nr_bc] = 1;
for (int sum=nr_ab + nr_ac + nr_bc;sum>=1;sum--){
for (i=0;i<=sum && i<=3*n;i++){
for (j=0;i+j<=sum && j<=3*n;j++){
k = sum - i - j;
if (k > 3*n || !dp[i][j][k]) /// nu am calculat starea asta
continue;
/// A -> B -> C -> A
int nr_ab = i, nr_ac = j, nr_bc = k, sol1, sol2, sol3;
for (int tip_a=0;tip_a<=1;tip_a++){
/// A -> B
int ok3 = 0;
if (nr_ab || nr_ac){
if (!tip_a){
if (nr_ab > 0){
sol1 = nr_ab;
nr_ab--;
ok3 = 1;
} else continue;
} else {
if (nr_ac > 0){
sol1 = nr_ac;
nr_ac--, nr_bc++;
ok3 = 1;
} else continue;
}
} else {
sol1 = 1; /// nu am ce sa dau mai departe
tip_a = 2;
}
for (int tip_b=0;tip_b<=1;tip_b++){
/// B -> C
int ok2 = 0;
if (nr_bc || nr_ab){
if (!tip_b){
if (nr_bc > 0){
sol2 = nr_bc;
nr_bc--;
ok2 = 1;
} else continue;
} else {
if (nr_ab > 0){
sol2 = nr_ab;
nr_ab--, nr_ac++;
ok2 = 1;
} else continue;
}
} else {
sol2 = 1;
tip_b = 2;
}
//if (nr_ab < 0 || nr_ac < 0 || nr_bc < 0)
// printf ("a");
for (int tip_c=0;tip_c<=1;tip_c++){
/// C -> A
int ok = 0;
if (nr_ac || nr_bc){
if (!tip_c){
if (nr_ac > 0){
sol3 = nr_ac;
nr_ac--;
ok = 1;
} else continue;
} else {
if (nr_bc > 0){
sol3 = nr_bc;
nr_bc--, nr_ab++;
ok = 1;
} else continue;
}
} else {
sol3 = 1;
tip_c = 2;
}
if (nr_ab + nr_ac + nr_bc < i + j + k){
//if (nr_ab < 0 || nr_ac < 0 || nr_bc < 0)
// printf ("a");
dp[nr_ab][nr_ac][nr_bc] += 1LL * dp[i][j][k] * sol1 % MOD * sol2 % MOD * sol3 % MOD;
if (dp[nr_ab][nr_ac][nr_bc] >= MOD)
dp[nr_ab][nr_ac][nr_bc] -= MOD;
//cout<<sol1*sol2*sol3<<"\n";
}
if (ok)
(!tip_c) ? (nr_ac++) : (nr_bc++, nr_ab--);
}
if (ok2)
(!tip_b) ? (nr_bc++) : (nr_ab++, nr_ac--);
}
/// reverse
if (ok3)
(!tip_a) ? (nr_ab++) : (nr_ac++, nr_bc--);
}}}}
cout<<dp[0][0][0]<<"\n";
}
return 0;
}
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 93 ms | 116856 KB | Output is correct |
| 2 | Correct | 124 ms | 117112 KB | Output is correct |
| 3 | Correct | 122 ms | 116856 KB | Output is correct |
| 4 | Correct | 123 ms | 116856 KB | Output is correct |
| 5 | Correct | 235 ms | 116856 KB | Output is correct |
| 6 | Correct | 279 ms | 116984 KB | Output is correct |
| 7 | Correct | 321 ms | 116984 KB | Output is correct |
| 8 | Correct | 385 ms | 116984 KB | Output is correct |
| 9 | Correct | 455 ms | 116988 KB | Output is correct |
| 10 | Correct | 564 ms | 116984 KB | Output is correct |