#include<cstdio>
int n, M, pv, cnt;
char p[22];
int w[13][22], D[2][1048576];
int Q[12][22][70100], Path[12][22][70100], tail[12][22];
void Ins(int x, int y, int a, int b, int num){
// printf("%d %d\n",a,b);
if(D[a][b])return;
D[a][b] = 1;
Q[x][y][++tail[x][y]] = b;
Path[x][y][tail[x][y]] = num;
}
void Do1(int mask, int x, int y, int nxt, int num){
if(y+2 < M && (mask >> (M-2)) == 7){
Ins(x, y, !pv, ((mask ^ (7 << (M-2))) << 1) | nxt, num);
}
if(y+1 < M && (mask >> (M-1)) == 3 && mask & 1){
Ins(x, y, !pv, ((mask ^ (3 << (M-1)) ^ 1) << 1) | nxt, num);
}
if(y+1 < M && (mask >> M) && (mask&1) && nxt){
Ins(x, y, !pv, (mask ^ (1 << M) ^ 1) << 1, num);
}
if(y && (mask >> M) && (mask&3) == 3){
Ins(x, y, !pv, ((mask ^ (1 << M) ^ 3) << 1) | nxt, num);
}
}
void Do2(int mask, int x, int y, int nxt, int num){
if(y+2 < M && (mask >> (M-2)) == 7){
Ins(x, y, !pv, ((mask ^ (7 << (M-2))) << 1) | nxt, num);
}
if(y+1 < M && (mask >> (M-1)) == 3 && nxt){
Ins(x, y, !pv, (mask ^ (3 << (M-1))) << 1, num);
}
}
int E[60][60], Col[60];
void Make(int a, int b){
if(a&&b&&a!=b)E[a][b]=E[b][a]=1;
}
bool v[7];
int main(){
int i, b, e, j, k;
scanf("%d",&n);
M = 4*n-1;
for(i=1;i<=n+n;i++){
if(i<=n)b = n-i, e = 3*n+i-2;
else b = i-n-1, e = 5*n-i-1;
scanf("%s",p+b);
for(j=b;j<=e;j++){
if(p[j]=='0')w[i][j] = 1;
}
}
int s = 0;
for(i=0;i<M;i++) if(w[1][i]) s += 1 << (M-i);
if(w[2][0])s++;
Ins(0,M-1,0,s,0);
int px = 0, py = M-1;
for(i=1;i<=n+n;i++){
for(j=0;j<M;j++){
int nxt = w[i+1][j+1];
if(j==M-1)nxt = w[i+2][0];
for(k=1;k<=tail[px][py];k++){
int t = Q[px][py][k];
if(t >> M){
if((n+i+j+1)&1) Do1(Q[px][py][k], i, j, nxt, k);
else Do2(Q[px][py][k], i, j, nxt, k);
}
else Ins(i, j, !pv, (t<<1) | nxt, k);
}
for(k=1;k<=tail[px][py];k++){
D[pv][Q[px][py][k]] = 0;
}
pv = !pv;
px = i, py = j;
}
}
if(!tail[n+n][M-1]){
puts("nemoguce");
return 0;
}
int x = 1;
for(i=n+n;i>=1;i--){
for(j=M-1;j>=0;j--){
int t = Q[i][j][x], tt = Path[i][j][x], y;
if(j)y = Q[i][j-1][tt];
else y = Q[i-1][M-1][tt];
if(y >> M){
int dif = y ^ (t >> 1);
if((dif >> (M-2)) == 7){
w[i][j]=w[i][j+1]=w[i][j+2]=++cnt;
}
else if((dif >> (M-1)) == 2){
if(dif & 2) w[i][j]=w[i+1][j]=w[i+1][j-1]=++cnt;
else w[i][j]=w[i+1][j]=w[i+1][j+1]=++cnt;
}
else if(dif & 1){
w[i][j]=w[i][j+1]=w[i+1][j]=++cnt;
}
else{
w[i][j]=w[i][j+1]=w[i+1][j+1]=++cnt;
}
}
x = tt;
}
}
for(i=1;i<=n+n;i++){
for(j=0;j<M;j++){
if(j)Make(w[i][j],w[i][j-1]);
Make(w[i][j],w[i][j+1]);
if((n+i+j+1)&1)Make(w[i][j],w[i+1][j]);
else Make(w[i][j],w[i-1][j]);
}
}
for(i=1;i<=cnt;i++){
for(j=1;j<=6;j++)v[j]=false;
for(j=1;j<=cnt;j++)if(E[i][j])v[Col[j]]=true;
for(j=1;j<=6;j++)if(!v[j])break;
Col[i]=j;
}
for(i=1;i<=n+n;i++){
if(i<=n)b = n-i, e = 3*n+i-2;
else b = i-n-1, e = 5*n-i-1;
for(j=b;j<=e;j++){
if(w[i][j])printf("%d",Col[w[i][j]]);
else printf(".");
}
printf("\n");
}
}
Compilation message
trapezi.cpp: In function 'int main()':
trapezi.cpp:42:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
trapezi.cpp:47:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",p+b);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
153908 KB |
Output is correct |
| 2 |
Correct |
0 ms |
153908 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
153908 KB |
Output is correct |
| 2 |
Correct |
0 ms |
153908 KB |
Output is correct |
| 3 |
Correct |
0 ms |
153908 KB |
Output is correct |
| 4 |
Correct |
0 ms |
153908 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
153908 KB |
Output is correct |
| 2 |
Correct |
0 ms |
153908 KB |
Output is correct |
| 3 |
Correct |
0 ms |
153908 KB |
Output is correct |
| 4 |
Correct |
0 ms |
153908 KB |
Output is correct |
| 5 |
Correct |
0 ms |
153908 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
153908 KB |
Output is correct |
| 2 |
Correct |
0 ms |
153908 KB |
Output is correct |
| 3 |
Correct |
0 ms |
153908 KB |
Output is correct |
| 4 |
Correct |
0 ms |
153908 KB |
Output is correct |
| 5 |
Correct |
0 ms |
153908 KB |
Output is correct |
| 6 |
Correct |
0 ms |
153908 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
39 ms |
153908 KB |
Output is correct |
| 2 |
Correct |
23 ms |
153908 KB |
Output is correct |
| 3 |
Correct |
0 ms |
153908 KB |
Output is correct |
| 4 |
Correct |
0 ms |
153908 KB |
Output is correct |
| 5 |
Correct |
9 ms |
153908 KB |
Output is correct |
| 6 |
Correct |
6 ms |
153908 KB |
Output is correct |
| 7 |
Correct |
9 ms |
153908 KB |
Output is correct |
| 8 |
Correct |
9 ms |
153908 KB |
Output is correct |
| 9 |
Correct |
13 ms |
153908 KB |
Output is correct |
| 10 |
Correct |
3 ms |
153908 KB |
Output is correct |
