Submission #646577

#	Time	Username	Problem	Language	Result	Execution time	Memory
646577		alextodoran	Nautilus (BOI19_nautilus)	C++17	100 / 100	126 ms	728 KiB

nautilus

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N, M, K;
    cin >> N >> M >> K;
    bitset <500> sea[N];
    for (int i = 0; i < N; i++) {
        string row;
        cin >> row;
        for (int j = 0; j < M; j++) {
            sea[i][j] = (row[j] == '.');
        }
    }

    bitset <500> dp[2][N];
    for (int i = 0; i < N; i++) {
        dp[0][i] = sea[i];
    }
    string path;
    cin >> path;
    for (int k = 1; k <= K; k++) {
        if (path[k - 1] == '?') {
            for (int i = 0; i < N; i++) {
                dp[k & 1][i] = ((dp[(k - 1) & 1][i] >> 1) | (dp[(k - 1) & 1][i] << 1));
                if (i > 0) {
                    dp[k & 1][i] |= dp[(k - 1) & 1][i - 1];
                }
                if (i < N - 1) {
                    dp[k & 1][i] |= dp[(k - 1) & 1][i + 1];
                }
            }
        } else {
            int di = 0, dj = 0;
            if (path[k - 1] == 'N') {
                dp[k & 1][N - 1].reset();
                for (int i = 0; i < N - 1; i++) {
                    dp[k & 1][i] = dp[(k - 1) & 1][i + 1];
                }
            } else if (path[k - 1] == 'E') {
                for (int i = 0; i < N; i++) {
                    dp[k & 1][i] = (dp[(k - 1) & 1][i] << 1);
                }
            } else if (path[k - 1] == 'S') {
                dp[k & 1][0].reset();
                for (int i = 1; i < N; i++) {
                    dp[k & 1][i] = dp[(k - 1) & 1][i - 1];
                }
            } else {
                for (int i = 0; i < N; i++) {
                    dp[k & 1][i] = (dp[(k - 1) & 1][i] >> 1);
                }
            }
        }
        for (int i = 0; i < N; i++) {
            dp[k & 1][i] &= sea[i];
        }
    }

    int answer = 0;
    for (int i = 0; i < N; i++) {
        answer += dp[K & 1][i].count();
    }
    cout << answer << "\n";

    return 0;
}

Compilation message (stderr)

nautilus.cpp: In function 'int main()':
nautilus.cpp:49:17: warning: unused variable 'di' [-Wunused-variable]
   49 |             int di = 0, dj = 0;
      |                 ^~
nautilus.cpp:49:25: warning: unused variable 'dj' [-Wunused-variable]
   49 |             int di = 0, dj = 0;
      |                         ^~

• Subtask 1: 29 / 29
• Subtask 2: 37 / 37
• Subtask 3: 34 / 34