Submission #491653

#	Time	Username	Problem	Language	Result	Execution time	Memory
491653		patrikpavic2	Sandwich (JOI16_sandwich)	C++17	35 / 100	5 ms	2212 KiB

sandwich

#include <cstdio>
#include <bitset>
#include <queue>
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std;

const int N = 55;

int n, m;
char A[N][N];
int jos[N][N][2], bio[N][N][2];
queue < pair < pair < int, int >, int > > Q;
bitset < N * N > koji[N * N][2];

inline int kod(int i, int j){
    return i * m + j;
}


void smanji(int i, int j, int k, int oi, int oj, int ok){
    jos[i][j][k]--; koji[kod(i, j)][k] |= koji[kod(oi, oj)][ok];
    if(!jos[i][j][k])
        Q.push({{i, j}, k});
}


int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            koji[kod(i, j)][0][kod(i, j)] = 1;
            koji[kod(i, j)][1][kod(i, j)] = 1;
            scanf(" %c", &A[i][j]);
            if(A[i][j] == 'Z'){
                jos[i][j][0] = (!!i) + (!!j); jos[i][j][1] = (!!(n - i - 1)) + (!!(m - j - 1));
            }
            else{
                jos[i][j][0] = (!!i) + (!!(m - j - 1)); jos[i][j][1] = (!!(n - i - 1)) + (!!j);
            }
        }
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            if(!jos[i][j][0]) Q.push({{i, j}, 0});
            if(!jos[i][j][1]) Q.push({{i, j}, 1});
        }
    }
    for(;!Q.empty();Q.pop()){
        int cx = Q.front().X.X, cy = Q.front().X.Y;
        int sm = Q.front().Y;
      //  printf("%d %d %d\n", cx, cy, sm);
        bio[cx][cy][sm] = 1;
        if(A[cx][cy] == 'N' && sm == 0){
            if(cy) smanji(cx, cy - 1, A[cx][cy - 1] == 'Z', cx, cy, sm);
            if(cx + 1 < n) smanji(cx + 1, cy, 0, cx, cy, sm);
        }
        if(A[cx][cy] == 'N' && sm == 1){
            if(cx) smanji(cx - 1, cy, 1, cx, cy, sm);
            if(cy + 1 < m) smanji(cx, cy + 1, A[cx][cy + 1] == 'N', cx, cy, sm);
        }
        if(A[cx][cy] == 'Z' && sm == 0){
            if(cx + 1 < n) smanji(cx + 1, cy, 0, cx, cy, sm);
            if(cy + 1 < m) smanji(cx, cy + 1, A[cx][cy + 1] == 'N', cx, cy, sm);
        }
        if(A[cx][cy] == 'Z' && sm == 1){
            if(cx) smanji(cx - 1, cy, 1, cx, cy, sm);
            if(cy) smanji(cx, cy - 1, A[cx][cy - 1] == 'Z', cx, cy, sm);
        }
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            int ans = N * N;
            if(bio[i][j][0]) ans = min(ans, (int)koji[kod(i, j)][0].count());
            if(bio[i][j][1]) ans = min(ans, (int)koji[kod(i, j)][1].count());
            printf("%d ", ans == N * N ? -1 : 2 * ans);
        }
        printf("\n");
    }
    return 0;
}

Compilation message (stderr)

sandwich.cpp: In function 'int main()':
sandwich.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
sandwich.cpp:38:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |             scanf(" %c", &A[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 35 / 35
• Subtask 2: 0 / 65