Submission #58328

#	Time	Username	Problem	Language	Result	Execution time	Memory
58328		patrikpavic2	Trapezi (COI17_trapezi)	C++17	63 / 100	1087 ms	62268 KiB

trapezi

#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 (stderr)

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);
                    ~~~~~^~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 22 / 22
• Subtask 5: 0 / 37