제출 #1319194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319194		penguin133	Nautilus (BOI19_nautilus)	C++17	66 / 100	1095 ms	824 KiB

nautilus

// Source: https://usaco.guide/general/io

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

	int r, c, m;
bitset <505*505> bs, def;
char a[505][505];
inline int conv(int x, int y) {
    return (x - 1) * c + y;
}
int main() {
    cin >> r >> c >> m;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            cin >> a[i][j];
            bs[conv(i, j)] = def[conv(i, j)] = 1;
            if (a[i][j] == '#') bs[conv(i, j)] = def[conv(i, j)] = 0;
        }
    }
    for (int i = 1; i <= m; i++) {
        char x; cin >> x;
        bitset <505*505> ok;
        if (x == 'S' || x == '?') {
            for (int j = 2; j <= r; j++) {
                int l1 = conv(j - 1, 1), r1 = conv(j - 1, c);
                int l2 = conv(j, 1), r2 = conv(j, c);
                //impose [l1, r1] onto [l2, r2]
                ok |= (bs<<(505*505-r1-1)>>(505*505-r1+l1-1)<<l2);
            }
        }
        if (x == 'N' || x == '?') {
            for (int j = 1; j < r; j++) {
                int l1 = conv(j + 1, 1), r1 = conv(j + 1, c);
                int l2 = conv(j, 1), r2 = conv(j, c);
                //impose [l1, r1] onto [l2, r2]
                ok |= (bs<<(505*505-r1-1)>>(505*505-r1+l1-1)<<l2);
            }
        }
        if (x == 'E' || x == '?') {
            for (int j = 1; j <= r; j++) {
                int l1 = conv(j, 1), r1 = conv(j, c - 1), l2 = conv(j, 2);
                ok |= (bs<<(505*505-r1-1)>>(505*505-r1+l1-1)<<l2);
            }
        }
        if (x == 'W' || x == '?') {
            for (int j = 1; j <= r; j++) {
                int l1 = conv(j, 2), r1 = conv(j, c), l2 = conv(j, 1);
                ok |= (bs<<(505*505-r1-1)>>(505*505-r1+l1-1)<<l2);
            }
        }
        ok &= def;
        bs = ok;
        /*
        for (int a = 1; a <= r; a++) {
            for (int b = 1; b <= c; b++) cout << bs[conv(a, b)];
            cout << '\n';
        }
        cout << '\n';
        */
    }
    cout << bs.count();
}

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