oj.uz

Submission #529734

# Submission time Handle Problem Language Result Execution time Memory
529734 2022-02-23T14:43:54 Z c28dnv9q3 Nautilus (BOI19_nautilus) C++17
0 / 100
 1 ms 204 KB 
#include <stdio.h>

typedef unsigned long long llong;

llong grid[8][505];
llong dp[2][8][505];

int main() {
    int R, C, M;
    scanf("%d %d %d", &R, &C, &M);
    int Rc = (R + 63) / 63;

    for(int r = 0; r < R; r++) {
        for(int c = 0; c < C; c++) {
            char chr;
            for(chr = getchar(); chr != '.' && chr != '#'; chr = getchar());
            if(chr == '.') {
                grid[r/64][c] |= 1 << (r % 64);
                dp[0][r/64][c] |= 1 << (r % 64);
            }
        }
    }

    int g = 1, pg = 0;
    for(int i = 0; i < M; i++) {
        char m;
        for(m = getchar();
            m != 'N' &&
            m != 'E' &&
            m != 'S' &&
            m != 'W' &&
            m != '?'
        ; m = getchar());

        for(int rc = 0; rc < Rc; rc++) {
            for(int c = 0; c < C; c++) {
                dp[g][rc][c] = 0;

                if((m == '?' || m == 'N')) dp[g][rc][c] |= (dp[pg][rc][c] >> 1) | ((rc < Rc-1) ? (dp[pg][rc+1][c] << 63) : 0);
                if((m == '?' || m == 'S')) dp[g][rc][c] |= (dp[pg][rc][c] << 1) | ((rc > 0) ? (dp[pg][rc-1][c] >> 63) : 0);

                if((m == '?' || m == 'E') && c > 0)   dp[g][rc][c] |= dp[pg][rc][c-1];
                if((m == '?' || m == 'W') && c < C-1) dp[g][rc][c] |= dp[pg][rc][c+1];

                dp[g][rc][c] &= grid[rc][c];
            }
        }

        // printf("%d %c:\n", i, m);
        // for(int r = 0; r < R; r++) {
        //     int rc = r/64, i = r%64;
        //     for(int c = 0; c < C; c++) {
        //         if(!(grid[rc][c] & (1 << i))) putchar('#');
        //         else if(dp[g][rc][c] & (1 << i)) putchar('X');
        //         else putchar('.');
        //     }
        //     puts("");
        // }
        // puts("");

        pg = g;
        g = (g+1) % 2;
    }

    int pc = 0;
    for(int r = 0; r < R; r++) {
        for(int c = 0; c < C; c++) {
            if(dp[pg][r/64][c] & (1 << (r % 64))) pc++;
        }
    }
    printf("%d\n", pc);

    return 0;
}

Compilation message

nautilus.cpp: In function 'int main()':
nautilus.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d %d %d", &R, &C, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -