Submission #58320

#TimeUsernameProblemLanguageResultExecution timeMemory
58320patrikpavic2Trapezi (COI17_trapezi)C++17
0 / 100
1028 ms741440 KiB
#include <cstdio> #include <cstring> #include <vector> using namespace std; const int N = 19; const int M = (1 << N); int a[N][N], n, rek[N*N][M], col[N][N], bio[N], naso = 0, fi[N],en[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][msk] != -1) return int(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(){ memset(rek,-1,sizeof(rek)); 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 (stderr)

trapezi.cpp: In function 'int main()':
trapezi.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
trapezi.cpp:98: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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...