oj.uz

Submission #491653

# Submission time Handle Problem Language Result Execution time Memory
491653 2021-12-03T17:24:25 Z patrikpavic2 Sandwich (JOI16_sandwich) C++17
35 / 100
 5 ms 2212 KB 
#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

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.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 288 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 2124 KB Output is correct
7 Correct 3 ms 1996 KB Output is correct
8 Correct 3 ms 2124 KB Output is correct
9 Correct 3 ms 1740 KB Output is correct
10 Correct 4 ms 2124 KB Output is correct
11 Correct 3 ms 2124 KB Output is correct
12 Correct 2 ms 1356 KB Output is correct
13 Correct 5 ms 2124 KB Output is correct
14 Correct 3 ms 2124 KB Output is correct
15 Correct 3 ms 2212 KB Output is correct
16 Correct 3 ms 2124 KB Output is correct
17 Correct 3 ms 2124 KB Output is correct
18 Correct 3 ms 2124 KB Output is correct
19 Correct 3 ms 2124 KB Output is correct
20 Correct 2 ms 2124 KB Output is correct
21 Correct 2 ms 2124 KB Output is correct
22 Correct 2 ms 2208 KB Output is correct
23 Correct 2 ms 2124 KB Output is correct
24 Correct 3 ms 2208 KB Output is correct
25 Correct 3 ms 2124 KB Output is correct
26 Correct 2 ms 2124 KB Output is correct
27 Correct 4 ms 2212 KB Output is correct
28 Correct 3 ms 2124 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 288 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 2124 KB Output is correct
7 Correct 3 ms 1996 KB Output is correct
8 Correct 3 ms 2124 KB Output is correct
9 Correct 3 ms 1740 KB Output is correct
10 Correct 4 ms 2124 KB Output is correct
11 Correct 3 ms 2124 KB Output is correct
12 Correct 2 ms 1356 KB Output is correct
13 Correct 5 ms 2124 KB Output is correct
14 Correct 3 ms 2124 KB Output is correct
15 Correct 3 ms 2212 KB Output is correct
16 Correct 3 ms 2124 KB Output is correct
17 Correct 3 ms 2124 KB Output is correct
18 Correct 3 ms 2124 KB Output is correct
19 Correct 3 ms 2124 KB Output is correct
20 Correct 2 ms 2124 KB Output is correct
21 Correct 2 ms 2124 KB Output is correct
22 Correct 2 ms 2208 KB Output is correct
23 Correct 2 ms 2124 KB Output is correct
24 Correct 3 ms 2208 KB Output is correct
25 Correct 3 ms 2124 KB Output is correct
26 Correct 2 ms 2124 KB Output is correct
27 Correct 4 ms 2212 KB Output is correct
28 Correct 3 ms 2124 KB Output is correct
29 Correct 1 ms 588 KB Output is correct
30 Runtime error 1 ms 460 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -