oj.uz

Submission #59010

# Submission time Handle Problem Language Result Execution time Memory
59010 2018-07-20T06:21:39 Z choikiwon Sandwich (JOI16_sandwich) C++17
0 / 100
 4 ms 648 KB 
#include<bits/stdc++.h>
using namespace std;

const int MN = 456;

int N, M;
char G[MN][MN];
queue<int> q;
int dist[MN * MN * 2], cnt[MN * MN * 2];

int f(int r, int c, int t) {
    return r * (2 * M) + c * 2 + t;
}

int main() {
    scanf("%d %d", &N, &M);

    for(int i = 0; i < N; i++) {
        scanf("\n");
        for(int j = 0; j < M; j++) {
            scanf("%c", &G[i][j]);
        }
    }

    for(int i = 0; i < M; i++) {
        cnt[ f(0, i, 1) ]++;
        cnt[ f(N - 1, i, 0) ]++;
    }
    for(int i = 0; i < N; i++) {
        cnt[ f(i, 0, G[i][0] == 'Z') ]++;
        cnt[ f(i, M - 1, G[i][M - 1] == 'N') ]++;
    }
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            for(int k = 0; k < 2; k++) {
                if(cnt[ f(i, j, k) ] == 2) {
                    dist[ f(i, j, k) ] = 1;
                    q.push(f(i, j, k));

                    //cout << i << ' ' << j << ' ' << k << endl;
                }
            }
        }
    }
    while(!q.empty()) {
        int u = q.front(); q.pop();

        int r = u / (2 * M);
        int c = (u % (2 * M)) / 2;
        int t = u % 2;

        //cout << r << ' ' << c << ' ' << t << ' ' << dist[u] << endl;

        if(!dist[ f(r, c, t ^ 1) ]) {
            dist[ f(r, c, t ^ 1) ] = dist[u] + 1;
            q.push(f(r, c, t ^ 1));
        }
        if(t) {
            int nr = r - 1;
            int nc = c;
            if(0 <= nr && !dist[ f(nr, nc, 0) ]) {
                cnt[ f(nr, nc, 0) ]++;
                if(cnt[ f(nr, nc, 0) ] == 2) {
                    dist[ f(nr, nc, 0) ] = dist[u] + 1;
                    q.push(f(nr, nc, 0));
                }
            }
        }
        else {
            int nr = r + 1;
            int nc = c;
            if(nr < N && !dist[ f(nr, nc, 1) ]) {
                cnt[ f(nr, nc, 1) ]++;
                if(cnt[ f(nr, nc, 1) ] == 2) {
                    dist[ f(nr, nc, 1) ] = dist[u] + 1;
                    q.push(f(nr, nc, 1));
                }
            }
        }
        if(t ^ (G[r][c] == 'N')) {
            int nr = r;
            int nc = c - 1;
            if(0 <= nc && !dist[ f(nr, nc, G[nr][nc] == 'N') ]) {
                cnt[ f(nr, nc, G[nr][nc] == 'N') ]++;
                if(cnt[ f(nr, nc, G[nr][nc] == 'N') ] == 2) {
                    dist[ f(nr, nc, G[nr][nc] == 'N') ] = dist[u] + 1;
                    q.push(f(nr, nc, G[nr][nc] == 'N'));
                }
            }
        }
        else {
            int nr = r;
            int nc = c + 1;
            if(nc < M && !dist[ f(nr, nc, G[nr][nc] == 'Z') ]) {
                cnt[ f(nr, nc, G[nr][nc] == 'Z') ]++;
                if(cnt[ f(nr, nc, G[nr][nc] == 'Z') ] == 2) {
                    dist[ f(nr, nc, G[nr][nc] == 'Z') ] = dist[u] + 1;
                    q.push(f(nr, nc, G[nr][nc] == 'Z'));
                }
            }
        }
    }

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(dist[ f(i, j, 0) ] && dist[ f(i, j, 1) ]) printf("%d ", min(dist[ f(i, j, 0) ], dist[ f(i, j, 1) ]) + 1);
            else printf("-1 ");
        }
        printf("\n");
    }
}

Compilation message

sandwich.cpp: In function 'int main()':
sandwich.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~
sandwich.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n");
         ~~~~~^~~~~~
sandwich.cpp:21:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%c", &G[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Incorrect 3 ms 648 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Incorrect 3 ms 648 KB Output isn't correct
6 Halted 0 ms 0 KB -