Submission #900615

#	Time	Username	Problem	Language	Result	Execution time	Memory
900615		Error42	Nautilus (BOI19_nautilus)	C++14	100 / 100	116 ms	848 KiB

nautilus

#include <bitset>
#include <iostream>
#include <vector>

using namespace std;

using map_t = vector<bitset<500>>;

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

    int r, c, m;
    cin >> r >> c >> m;

    map_t map(500);

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            char ch;
            cin >> ch;

            if (ch == '.')
                map[i][j] = true;
        }
    }

    string s;
    cin >> s;

    map_t cur = map;
    map_t next(500);

    for (char const& ch : s) {
        switch (ch) {
        case 'N':
            for (int i = 0; i < r - 1; i++) {
                cur[i] = cur[i + 1];
                cur[i] &= map[i];
            }
            cur[r - 1].reset();
            break;
        case 'S':
            for (int i = r - 1; i > 0; i--) {
                cur[i] = cur[i - 1];
                cur[i] &= map[i];
            }
            cur[0].reset();
            break;
        case 'E':
        case 'W':
            for (int i = 0; i < r; i++) {
                // indices are swapped, so the shift direction is swapped
                if (ch == 'E')
                    cur[i] <<= 1;
                else
                    cur[i] >>= 1;
                cur[i] &= map[i];
            }
            break;
        case '?':
            for (int i = 0; i < r; i++) {
                next[i].reset();

                if (i > 0)
                    next[i] |= cur[i - 1];
                if (i + 1 < r)
                    next[i] |= cur[i + 1];
                next[i] |= cur[i] << 1;
                next[i] |= cur[i] >> 1;

                next[i] &= map[i];
            }

            swap(next, cur);
            break;
        }

#ifdef _DEBUG
        cout << ch << ":\n";
        
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (!map[i][j])
                    cout << "#";
                else if (cur[i][j])
                    cout << "X";
                else
                    cout << ".";
            }
            cout << "\n";
        }
#endif
    }

    int ans = 0;
    for (int i = 0; i < r; i++)
        ans += cur[i].count();

    cout << ans << "\n";
}

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