Submission #680766

#	Time	Username	Problem	Language	Result	Execution time	Memory
680766		four_specks	Nautilus (BOI19_nautilus)	C++17	100 / 100	205 ms	1276 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;

namespace
{
} // namespace

using BS = bitset<250'000>;

void solve()
{
    int r, c, m;
    cin >> r >> c >> m;

    vector<string> grid(r);
    for (string &row : grid)
        cin >> row;

    string s;
    cin >> s;

    BS base;
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            if (grid[i][j] == '.')
                base[i * c + j] = 1;
        }
    }

    BS lft = base, rgt = base;
    for (int i = 0; i < r; i++)
        lft[i * c] = 0;
    for (int i = 0; i < r; i++)
        rgt[i * c + c - 1] = 0;

    BS can = base;
    for (char x : s)
    {
        if (x == 'N')
            can = (can >> c) & base;
        else if (x == 'W')
            can = ((can & lft) >> 1) & base;
        else if (x == 'E')
            can = ((can & rgt) << 1) & base;
        else if (x == 'S')
            can = (can << c) & base;
        else
            can = ((can >> c) | ((can & rgt) << 1) | ((can & lft) >> 1) | (can << c)) & base;
    }

    cout << can.count() << '\n';
}

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

    solve();

    return 0;
}

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