#include <cstdio>
#include <cstring>
#include <vector>
#include <unordered_map>
using namespace std;
const int N = 20;
const int M = (1 << N);
int a[N][N], n, col[N][N], bio[N], naso = 0, fi[N],en[N];
unordered_map < int, int> rek[N *N];
const int px[4] = {0,0,1,-1};
const int py[4] = {1,-1,0,0};
bool boj(int c){
if(c < 0) return 0;
return (bool)a[c / (4 * n - 1)][c % (4 * n - 1)];
}
int f(int c,int msk){
if(boj(c - 4 * n - 1) && !((1 << (4 * n)) & msk)) {
return 0;
}
/**
if(((1 << (4 * n)) & msk))
msk ^= (1 << (4 * n));
**/
if(rek[c].count(msk) != 0) return (rek[c][msk] != -2);
rek[c][msk] = -2;
int rmsk = msk;
msk *= 2;
if(c >= (4 * n - 1) * (2 * n)){
// printf("KRAJ\n");
rek[c][rmsk] = msk & ((1 << (4 * n + 1)) - 1);
for(int i = 1;i<=4 * n;i++){
if(boj(c - i) && !(msk & (1 << i))) {
rek[c][rmsk] = -2;
//printf("NIJE DOBAR %d\n", c - i);
return 0;
}
}
naso= 1;
return 1;
}
if(boj(c)){
if((c % (4 * n - 1) % 2 + c / (4 * n - 1) % 2 + (n ) % 2) % 2 == 0){
if(boj(c - (4 * n - 1)) && boj(c - (4 * n)) && !(msk&(1 << (4 * n))) && !(msk&(1 << (4 * n - 1))) && c % (4 * n - 1) != 0){
msk ^= (1 << (4 * n)) | (1 << (4 * n - 1));
if( f(c + 1, (msk | 1) & ((1 << (4 * n + 1)) - 1))){
rek[c][rmsk] = (msk | 1) & ((1 << (4 * n + 1)) - 1);
}
msk ^= (1 << (4 * n)) | (1 << (4 * n - 1));
}
if(boj(c - (4 * n - 1)) && boj(c - (4 * n - 2)) && !(msk&(1 << (4 * n - 2))) && !(msk&(1 << (4 * n - 1))) && c % (4 * n - 1) != 4 * n - 2){
msk ^= (1 << (4 * n - 2)) | (1 << (4 * n - 1));
if(f(c + 1, (msk | 1) & ((1 << (4 * n + 1)) - 1)) ){
rek[c][rmsk] = (msk | 1) & ((1 << (4 * n + 1)) - 1);
}
msk ^= (1 << (4 * n - 2)) | (1 << (4 * n - 1));
}
if(boj(c - 1) && boj(c - (4 * n - 1)) && !(msk&(1 << (4 * n - 1))) && !(msk&2) && c % (4 * n - 1) != 0){
msk ^= 2 | (1 << (4 * n - 1));
if(f(c + 1, (msk | 1) & ((1 << (4 * n + 1)) - 1)) ){
rek[c][rmsk] = (msk | 1) & ((1 << (4 * n + 1)) - 1);
}
msk ^= 2 | (1 << (4 * n - 1));
}
}
else{
if(boj(c - 1) && boj(c - (4 * n)) && !(msk&2) && !(msk&(1 << (4 * n))) && c % (4 * n - 1) != 0){
msk ^= 2 | (1 << (4 * n));
if(f(c + 1, (msk | 1) & ((1 << (4 * n + 1)) - 1))){
rek[c][rmsk] = (msk | 1) & ((1 << (4 * n + 1)) - 1);
}
msk ^= 2 | (1 << (4 * n));
}
}
if(boj(c - 1) && boj(c - 2) && !(msk&2) && !(msk&4) && c % (4 * n - 1) > 1){
if(f(c + 1, ((msk | 1) & ((1 << (4 * n + 1)) - 1)) ^ 6) ){
rek[c][rmsk] = ((msk | 1) & ((1 << (4 * n + 1)) - 1)) ^ 6;
}
}
}
if(f(c + 1, msk & ( (1 << (4 * n + 1)) - 1)) ){
rek[c][rmsk] = msk & ( (1 << (4 * n + 1)) - 1);
}
msk /=2;
//printf("REK %d\n", rek[c][msk]);
//printf("%d %d => %d\n", c, msk,rek[c][msk]);
return int(rek[c][msk] != -2);
}
int main(){
scanf("%d", &n);
int k = n - 1;
for(int i = 0;i<2 * n;i++){
for(int j = k;j<4 * n - 1 - k;j++){
char c;scanf(" %c", &c);
if(c == '0') a[i][j] = 1;
}
if(i < n - 1) k--;
if(i >= n) k++;
}
f(0,0);
//printf("%d\n", naso);
if(rek[0][0] == -2){
printf("nemoguce\n");
return 0;
}
int msk = 0, olmsk = 0;
for(int i = 0;i<=(4 * n - 1) * (2 * n);i++){
msk = rek[i][msk];
//printf("XOR %d => %d\n", olmsk , msk);
if(msk & 1){
olmsk = (olmsk << 1) & ( (1 << (4 * n + 1)) - 1);
vector < int > trb;
for(int j = 0;j<4 * n + 5;j++){
if((1 << j) & (olmsk ^ msk)){
int c = i - j,cx = c / (4 * n - 1), cy = c % (4 * n - 1);
//printf("BOJAM %d %d U %d\n", cx, cy, i);
for(int k = 0;k<4;k++){
int nx = cx + px[k], ny = cy + py[k];
if(nx < 0 || ny < 0 || nx >= 2 * n || ny >= 4 * n - 1) continue;
bio[col[nx][ny]]++;//printf("COL %d\n",col[nx][ny]);
}
trb.push_back(c);
}
}
int koja = 1;
while(bio[koja]) koja++;
memset(bio,0,sizeof(bio));
for(int x : trb){
col[x/(4 * n - 1)][x % (4 * n - 1)] = koja;
}
}
olmsk = msk;
}
k = n - 1;
for(int i = 0;i<2 * n;i++){
//for(int j = 0;j<k;j++) printf(" ");
for(int j = k;j<4 * n - 1 - k;j++){
if(col[i][j] == 0) printf(".");
else printf("%d", col[i][j]);
}
printf("\n");
if(i < n - 1) k--;
if(i >= n) k++;
}
}
Compilation message
trapezi.cpp: In function 'int main()':
trapezi.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
trapezi.cpp:99:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
char c;scanf(" %c", &c);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
488 KB |
Output is correct |
| 2 |
Correct |
3 ms |
492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
612 KB |
Output is correct |
| 4 |
Correct |
3 ms |
668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
704 KB |
Output is correct |
| 2 |
Correct |
3 ms |
704 KB |
Output is correct |
| 3 |
Correct |
2 ms |
704 KB |
Output is correct |
| 4 |
Correct |
3 ms |
748 KB |
Output is correct |
| 5 |
Correct |
2 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
1772 KB |
Output is correct |
| 2 |
Correct |
56 ms |
5484 KB |
Output is correct |
| 3 |
Correct |
2 ms |
5484 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5484 KB |
Output is correct |
| 5 |
Correct |
32 ms |
5484 KB |
Output is correct |
| 6 |
Correct |
4 ms |
5484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1087 ms |
62268 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
