Submission #896136

#	Time	Username	Problem	Language	Result	Execution time	Memory
896136		box	Nautilus (BOI19_nautilus)	C++17	100 / 100	161 ms	1112 KiB

nautilus

#include <bits/stdc++.h>
using namespace std;

#define ar array
#define all(v) begin(v), end(v)
#define sz(v) int(std::size(v))
using i64 = long long;
using u64 = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int MAXN = 500, BIT = 64, FULL = 63;
const int NUM = MAXN / BIT + 1;
const i64 FIRST = (1LL << 0), LAST = (1LL << 63);

int N, M, K;
string T;
u64 good[MAXN][NUM];
u64 ok[MAXN][NUM];
u64 transition[4][MAXN][NUM];
bool flip;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M >> K;
    if (N > M) flip = 1;
    for (int i = 0; i < (flip ? M : N); i++) for (int j = 0; j < (flip ? N : M); j++)
        good[i][j / BIT] |= 1LL << (j & FULL);
    for (int i = 0; i < N; i++) {
        string S; cin >> S;
        for (int j = 0; j < M; j++) if (S[j] == '#') {
            if (flip) good[j][i / BIT] ^= 1LL << (i & FULL);
            else good[i][j / BIT] ^= 1LL << (j & FULL);
        }
    }
    cin >> T;
    for (char &c : T) if (flip && c != '?') {
        if (c == 'W') c = 'N';
        else if (c == 'E') c = 'S';
        else if (c == 'N') c = 'W';
        else if (c == 'S') c = 'E';
    }
    if (flip) swap(N, M);
    // reverse(begin(T), end(T));
    int BLOCKS = (M - 1) / BIT + 1;
    for (int i = 0; i < N; i++) for (int j = 0; j < BLOCKS; j++)
        ok[i][j] = good[i][j];
    auto print = [&]() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < BLOCKS; j++)
                for (int k = 0; k < BIT; k++)
                    cerr << (ok[i][j] >> k & 1);
            cerr << endl;
        }
        cerr << endl;
    };
    // print();
    for (char c : T) {
        static bool f[4];
        fill(f, f + 4, false);
        if (c == 'S' || c == '?') {
            f[0] = 1;
            for (int i = 0; i < N; i++) for (int j = 0; j < BLOCKS; j++)
                transition[0][i][j] = i == 0 ? 0 : ok[i - 1][j];
        }
        if (c == 'N' || c == '?') {
            f[1] = 1;
            for (int i = 0; i < N; i++) for (int j = 0; j < BLOCKS; j++)
                transition[1][i][j] = i == N - 1 ? 0 : ok[i + 1][j];
        }
        if (c == 'E' || c == '?') {
            f[2] = 1;
            for (int i = 0; i < N; i++) for (int j = 0; j < BLOCKS; j++) {
                transition[2][i][j] = ok[i][j] << 1;
                if (j && (ok[i][j - 1] & LAST)) transition[2][i][j] |= FIRST;
            }
        }
        if (c == 'W' || c == '?') {
            f[3] = 1;
            for (int i = 0; i < N; i++) for (int j = 0; j < BLOCKS; j++) {
                transition[3][i][j] = ok[i][j] >> 1;
                if (j != BLOCKS - 1 && (ok[i][j + 1] & FIRST)) transition[3][i][j] |= LAST;
            }
        }
        for (int i = 0; i < N; i++) for (int j = 0; j < BLOCKS; j++) {
            ok[i][j] = 0;
            if (f[0]) ok[i][j] |= transition[0][i][j];
            if (f[1]) ok[i][j] |= transition[1][i][j];
            if (f[2]) ok[i][j] |= transition[2][i][j];
            if (f[3]) ok[i][j] |= transition[3][i][j];
            ok[i][j] &= good[i][j];
        }
        // print();
    }
    int tot = 0;
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) if (ok[i][j / BIT] >> (j & FULL) & 1)
        tot++;
    cout << tot << '\n';
}

Compilation message (stderr)

nautilus.cpp: In function 'int main()':
nautilus.cpp:49:10: warning: variable 'print' set but not used [-Wunused-but-set-variable]
   49 |     auto print = [&]() {
      |          ^~~~~

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