oj.uz

Submission #703497

# Submission time Handle Problem Language Result Execution time Memory
703497 2023-02-27T14:08:40 Z bebra Nautilus (BOI19_nautilus) C++17
66 / 100
 960 ms 262144 KB 
#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.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 13396 KB Output is correct
2 Correct 9 ms 13396 KB Output is correct
3 Correct 9 ms 13276 KB Output is correct
4 Correct 7 ms 12820 KB Output is correct
5 Correct 6 ms 10068 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 13396 KB Output is correct
2 Correct 9 ms 13396 KB Output is correct
3 Correct 9 ms 13276 KB Output is correct
4 Correct 7 ms 12820 KB Output is correct
5 Correct 6 ms 10068 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 17 ms 13508 KB Output is correct
8 Correct 10 ms 13236 KB Output is correct
9 Correct 8 ms 12500 KB Output is correct
10 Correct 6 ms 10068 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 19 ms 13508 KB Output is correct
13 Correct 16 ms 13352 KB Output is correct
14 Correct 16 ms 13268 KB Output is correct
15 Correct 8 ms 10068 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 21 ms 13492 KB Output is correct
18 Correct 18 ms 13380 KB Output is correct
19 Correct 24 ms 12560 KB Output is correct
20 Correct 16 ms 10080 KB Output is correct
21 Correct 1 ms 468 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 13396 KB Output is correct
2 Correct 9 ms 13396 KB Output is correct
3 Correct 9 ms 13276 KB Output is correct
4 Correct 7 ms 12820 KB Output is correct
5 Correct 6 ms 10068 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 17 ms 13508 KB Output is correct
8 Correct 10 ms 13236 KB Output is correct
9 Correct 8 ms 12500 KB Output is correct
10 Correct 6 ms 10068 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 19 ms 13508 KB Output is correct
13 Correct 16 ms 13352 KB Output is correct
14 Correct 16 ms 13268 KB Output is correct
15 Correct 8 ms 10068 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 21 ms 13492 KB Output is correct
18 Correct 18 ms 13380 KB Output is correct
19 Correct 24 ms 12560 KB Output is correct
20 Correct 16 ms 10080 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Runtime error 960 ms 262144 KB Execution killed with signal 9
23 Halted 0 ms 0 KB -