| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 331817 | 2020-11-30T09:25:49 Z | Ruxandra985 | Fishing Game (RMI19_fishing) | C++14 | 607 ms | 109420 KB |
/**
* user: nanu-c77
* fname: Ruxandra Laura
* lname: Nanu
* task: fishing
* score: 100.0
* date: 2019-10-11 10:11:34.727415
*/
#include <cstdio>
#include <cstring>
#define MOD 1000000007
using namespace std;
int fa[400],fb[400],fc[400],sol,n,f0[10][10],f1[10][10],f2[10][10];
int dp[310][310][310];
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int t,i,x,xi,yi,zi,xc,yc,zc,y,z,sum,j,k,mask;
int dinm,ok;
//printf ("%d" , (! (! (-1))));
fscanf (fin,"%d%d",&n,&t);
for (;t;t--){
for (i=0;i<=3*n;i++)
fa[i] = fb[i] = fc[i] = 0;
for (i=1;i<=2*n;i++){
fscanf (fin,"%d",&x);
fa[x] = (fa[x]+1)%2;
}
for (i=1;i<=2*n;i++){
fscanf (fin,"%d",&x);
fb[x] = (fb[x]+1)%2;
}
for (i=1;i<=2*n;i++){
fscanf (fin,"%d",&x);
fc[x] = (fc[x]+1)%2;
}
xi = yi = zi = 0;
for (i=1;i<=3*n;i++){
if (fa[i] && fb[i])
xi++;
else if (fb[i] && fc[i])
yi++;
else if (fa[i] && fc[i])
zi++;
}
for (i=0;i<=3*n;i++){
for (j=0;j<=3*n;j++){
memset(dp[i][j] , 0 , sizeof(dp[i][j]));
}
}
dp[xi][yi][zi] = 1;
for (sum = xi+yi+zi ; sum ; sum--){
for (x=0;x<=sum && x<=3*n ;x++){
for (y=0;y+x<=sum && y<=3*n;y++){
z = sum - x - y;
if (z>3*n || !dp[x][y][z])
continue;
for (i=0;i<5;i++)
for (j=0;j<5;j++)
f0[i][j] = f1[i][j] = f2[i][j] = 0;
/// acum ai x y z, vrei sa vezi ce alte stari obtii
/// caz 1 : 12
xc = x;
yc = y;
zc = z;
ok = 1;
//if (x == 1 && y == 1 && z == 1)
// printf ("a");
for (mask=0;mask<8;mask++){
i = 2 + (mask & 1);
j = (mask & 2) + 1;
k = ( 1 + ((mask & 4)!=0) );
if (i!=3 || j!=1 || k!=2){
xc = x;
yc = y;
zc = z;
ok = 1;
dinm = 1;
if (xc || zc){ /// ai ceva in 1 , nu ii da skip la turn
if (i==2){
dinm = dinm * xc;
ok = (ok & (! (! xc ) ) );
//if (!xc)
// ok = 0;
xc--;
}
else {
dinm = dinm * zc;
ok = (ok & (! (! zc ) ) );
zc--;
yc++;
}
}
else {
ok = (ok & (!f0[j][k]));
f0[j][k] = (f0[j][k] | ok);
}
if (yc || xc){ /// ai ceva in 2 , nu ii da skip la turn
if (j==1){ /// 2 ii da lui 3 un 12
dinm = dinm * xc;
zc++;
ok = (ok & (! (! xc ) ) );
xc--;
}
else { /// 2 ii da lui 3 un 23
dinm = dinm * yc;
ok = (ok & (! (! yc ) ) );
yc--;
}
}
else {
ok = (ok & (!f1[i][k]));
f1[i][k] = (f1[i][j] | ok);
}
if (yc || zc){ /// ai ceva in z , nu ii dai skip la turn
if (k==1){ /// 3 ii da lui 1 un 13
dinm = dinm * zc;
ok = (ok & (! (! zc ) ) );
zc--;
}
else { /// 3 ii da lui 1 un 23
dinm = dinm * yc;
ok = (ok & (! (! yc ) ) );
yc--;
xc++;
}
}
else {
ok = (ok & (!f2[i][j]));
f2[i][j] = (f2[i][j] | ok);
}
/// inca esti aici => schimb valid
if (x + y + z <= xc + yc + zc) /// nu s a eliminat la runda
ok = 0;
if (ok){
dp[xc][yc][zc] = (dp[xc][yc][zc] + (dinm*1LL * dp[x][y][z])%MOD);
if (dp[xc][yc][zc] >= MOD)
dp[xc][yc][zc]-=MOD;
}
}
}
}
}
}
fprintf (fout,"%d\n",dp[0][0][0]);
}
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 364 KB | Output is correct |
| 2 | Correct | 1 ms | 492 KB | Output is correct |
| 3 | Correct | 2 ms | 1644 KB | Output is correct |
| 4 | Correct | 6 ms | 5100 KB | Output is correct |
| 5 | Correct | 99 ms | 28652 KB | Output is correct |
| 6 | Correct | 165 ms | 40852 KB | Output is correct |
| 7 | Correct | 241 ms | 55276 KB | Output is correct |
| 8 | Correct | 332 ms | 71788 KB | Output is correct |
| 9 | Correct | 443 ms | 90548 KB | Output is correct |
| 10 | Correct | 607 ms | 109420 KB | Output is correct |