Submission #725603

#	Time	Username	Problem	Language	Result	Execution time	Memory
725603		_martynas	Nautilus (BOI19_nautilus)	C++14	100 / 100	334 ms	1772 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;

const int MXN = 505;

int r, c, m;

string A[MXN], moves;
bitset<MXN*MXN> water, poss, first_col, first_row, last_col, last_row;

int main() {
    cin >> r >> c >> m;
    for(int i = 0; i < r; i++) {
        cin >> A[i];
        for(int j = 0; j < c; j++) {
            if(A[i][j] == '.') water[i*c+j] = 1;
        }
    }
    for(int i = 0; i < r; i++) {
        first_col[i*c] = 1;
        last_col[i*c+c-1] = 1;
    }
    for(int i = 0; i < c; i++) {
        first_row[i] = 1;
        last_row[(r-1)*c+i] = 1;
    }
    poss = water;
    cin >> moves;
    for(int i = 0; i < m; i++) {
        switch(moves[i]) {
        case 'N':
            poss = ((poss & ~first_row) >> c) & water;
            break;
        case 'E':
            poss = ((poss & ~last_col) << 1) & water;
            break;
        case 'S':
            poss = ((poss & ~last_row) << c) & water;
            break;
        case 'W':
            poss = ((poss & ~first_col) >> 1) & water;
            break;
        case '?':
            poss =
            (((poss & ~first_row) >> c) |
            ((poss & ~last_col) << 1) |
            ((poss & ~last_row) << c) |
            ((poss & ~first_col) >> 1))
            & water;
            break;
        default:
            assert(false);
        }
    }
    cout << poss.count() << "\n";
    return 0;
}

/*
3 3 1
...
.#.
...
E


*/

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