Submission #1273762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273762		phungha	Nautilus (BOI19_nautilus)	C++20	100 / 100	92 ms	816 KiB

nautilus

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("test36.in", "r", stdin);
    //freopen("test01.out", "w", stdout);
    int r, c, m;
    cin >> r >> c >> m;
    string a[r], s;
    for (int i = 0; i < r; i++)
        cin >> a[i];
    cin >> s;
    // sea[i]: mặt nạ ô nước của hàng i (1 = nước, 0 = đảo)
    // reach[i]: các cột có thể đứng ở hàng i hiện tại
    // tmp[i]: tạm dùng khi ký tự là ?
    bitset<500> sea[r], reach[r], tmp[r];
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++) // đảo cột j -> c - 1 - j khi gán vào bitset
            // nếu không đảo, hướng trái/phải sẽ bị ngược trực giác khi dùng shift
            sea[i][j] = reach[i][j] = (a[i][c - 1 - j] == '.');
    for (char c: s) {
        if (c == 'W') {
            for (int i = 0; i < r; ++i)
                reach[i] = (reach[i] << 1) & sea[i];
        }
        if (c == 'E') {
            for (int i = 0; i < r; ++i)
                reach[i] = (reach[i] >> 1) & sea[i];
        }
        if (c == 'N') {
            // để vào ô hàng i trước đó phải ở hàng i + 1
            // duyệt i từ nhỏ đến lớn nên reach[i + 1] chưa bị ghi đè => đảm bảo dùng trạng thái cũ
            for (int i = 0; i < r; ++i)
                if (i + 1 < r)
                    reach[i] = reach[i + 1] & sea[i];
                else
                    reach[i].reset(); // hàng cuối cùng i = r - 1 không thể đến được
        }
        if (c == 'S') {
            // để vào ô hàng i trước đó phải ở hàng i - 1
            // duyệt i từ lớn đến nhỏ nên reach[i - 1] chưa bị ghi đè => đảm bảo dùng trạng thái cũ
            for (int i = r - 1; i >= 0; i--)
                if (i > 0)
                    reach[i] = reach[i - 1] & sea[i];
                else
                    reach[i].reset(); // hàng trên cùng i = 0 không thể đến được
        }
        if (c == '?') { // bất kỳ hướng
            for (int i = 0; i < r; i++) {
                // dùng mảng tmp để tính, vì còn dùng trạng thái cũ
                tmp[i] = (reach[i] << 1) | (reach[i] >> 1); // hướng W, E
                if (i > 0) tmp[i] |= reach[i - 1];          // hướng S
                if (i + 1 < r) tmp[i] |= reach[i + 1];      // hướng N
                tmp[i] &= sea[i];
            }
            for (int i = 0; i < r; i++)
                reach[i] = tmp[i];
        }
    }
    int ans = 0;
    for (int i = 0; i < r; i++)
        ans += reach[i].count();
    cout << ans << "\n";
    return 0;
}

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