Submission #703497

#	Time	Username	Problem	Language	Result	Execution time	Memory
703497		bebra	Nautilus (BOI19_nautilus)	C++17	66 / 100	960 ms	262144 KiB

nautilus

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

#define dbg(x) cerr << #x << ": " << x << endl;

const int MAX_N = 500 + 5;
const int MAX_M = 5000 + 5;
string a[MAX_N];

bitset<MAX_M> used[MAX_N][MAX_N];
bitset<MAX_M> res[MAX_N][MAX_N];


vector<pair<int, int>> delta = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};


mt19937 rng(random_device{}());


bool can(int i, int j, int pos, int n, int m, const string& s) {
    if (i < 0 || i >= n || j < 0 || j >= m || a[i][j] == '#') {
        return false;
    }
    if (used[i][j].test(pos)) {
        return res[i][j].test(pos);
    }

    if (pos == (int)s.size()) {
        res[i][j].set(pos);
        return true;
    }

    auto c = s[pos];
    used[i][j].set(pos);

    if (c == 'N') {
        res[i][j][pos] = can(i - 1, j, pos + 1, n, m, s);
    } else if (c == 'S') {
        res[i][j][pos] = can(i + 1, j, pos + 1, n, m, s);
    } else if (c == 'W') {
        res[i][j][pos] = can(i, j - 1, pos + 1, n, m, s);
    } else if (c == 'E') {
        res[i][j][pos] = can(i, j + 1, pos + 1, n, m, s);
    } else {
        auto d = delta;
        shuffle(d.begin(), d.end(), rng);
        for (const auto& [di, dj] : d) {
            res[i][j].set(pos, can(i + di, j + dj, pos + 1, n, m, s));
            if (res[i][j].test(pos)) return true;
        }
    }
    return res[i][j][pos];
}

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

    int n, m, t;
    cin >> n >> m >> t;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    for (auto& c : s) {
        if (c == 'N') {
            c = 'S';
        } else if (c == 'S') {
            c = 'N';
        } else if (c == 'W') {
            c = 'E';
        } else if (c == 'E') {
            c = 'W';
        }
    }
    int ans = 0;
    // reverse the operations and check if there exists at least one starting position
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == '#') continue;
            if (can(i, j, 0, n, m, s)) ++ans;
        }
    }
    cout << ans << '\n';

    
    return 0;
}

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