oj.uz

Submission #996431

# Submission time Handle Problem Language Result Execution time Memory
996431 2024-06-10T15:05:08 Z yanb Snake Escaping (JOI18_snake_escaping) C++14
12 / 100
 2000 ms 23816 KB 
#include <bits/stdc++.h>
    
using namespace std;
    
#define int long long
#define pii pair<long long, long long>
#define t3i tuple<long long, long long, long long>

const int MinVop = 10;

int calc(vector<int> &tri, int x, int l, string &tox) {
    if (l == x) {
        int v = 0;
        for (int i = 0; i < l; i++) {
            v *= 2;
            v += tri[i];
        }
        return tox[v] - '0';
    }
    if (tri[x] == 2) {
        int ans = 0;
        tri[x] = 0;
        ans += calc(tri, x + 1, l, tox);
        tri[x] = 1;
        ans += calc(tri, x + 1, l, tox);
        tri[x] = 2;
        return ans;
    }
    return calc(tri, x + 1, l, tox);
}

int build(vector<int> &tri, vector<int> &ans, string &tox, int l, int q) {
    int v = 0, vop = 0;
    for (int i = 0; i < l; i++) {
        v *= 3;
        v += tri[i];
        vop += (tri[i] == 2);
    }

    if (vop < MinVop) {
        vector<int> tri_(l);
        for (int i = 0; i < l; i++) tri_[i] = tri[i];
        ans[v] = calc(tri_, 0, l, tox);
    }

    if (ans[v] != -1) return ans[v];

    for (int i = 0; i < l; i++) {
        if (tri[i] == 2) {
            int cans = 0;
            tri[i] = 0;
            cans += build(tri, ans, tox, l, q);
            tri[i] = 1;
            cans += build(tri, ans, tox, l, q);
            tri[i] = 2;
            ans[v] = cans;
        }
    }

    return ans[v];
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int l, q;
    string tox;
    cin >> l >> q >> tox;
    
    vector<int> ans(pow(3, l) + 100, -1);
    vector<int> tri(l, 2);
    build(tri, ans, tox, l, q);

    while (q--) {
        string s;
        cin >> s;
        int v = 0, vop = 0;
        for (int i = 0; i < l; i++) {
            v *= 3;
            v += (s[i] == '?' ? 2 : s[i] - '0');
            vop += (s[i] == '?');
        }

        if (vop >= MinVop) {
            cout << ans[v] << "\n";
        } else {
            vector<int> tri(l);
            for (int i = 0; i < l; i++) tri[i] = (s[i] == '?' ? 2 : s[i] - '0');
            cout << calc(tri, 0, l, tox) << "\n";
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 599 ms 10564 KB Output is correct
12 Correct 877 ms 10168 KB Output is correct
13 Correct 265 ms 9340 KB Output is correct
14 Correct 249 ms 9556 KB Output is correct
15 Correct 823 ms 10576 KB Output is correct
16 Correct 395 ms 9752 KB Output is correct
17 Correct 406 ms 9560 KB Output is correct
18 Correct 101 ms 11344 KB Output is correct
19 Correct 127 ms 8396 KB Output is correct
20 Correct 853 ms 10064 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 599 ms 10564 KB Output is correct
12 Correct 877 ms 10168 KB Output is correct
13 Correct 265 ms 9340 KB Output is correct
14 Correct 249 ms 9556 KB Output is correct
15 Correct 823 ms 10576 KB Output is correct
16 Correct 395 ms 9752 KB Output is correct
17 Correct 406 ms 9560 KB Output is correct
18 Correct 101 ms 11344 KB Output is correct
19 Correct 127 ms 8396 KB Output is correct
20 Correct 853 ms 10064 KB Output is correct
21 Execution timed out 2009 ms 23816 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Runtime error 5 ms 3584 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 599 ms 10564 KB Output is correct
12 Correct 877 ms 10168 KB Output is correct
13 Correct 265 ms 9340 KB Output is correct
14 Correct 249 ms 9556 KB Output is correct
15 Correct 823 ms 10576 KB Output is correct
16 Correct 395 ms 9752 KB Output is correct
17 Correct 406 ms 9560 KB Output is correct
18 Correct 101 ms 11344 KB Output is correct
19 Correct 127 ms 8396 KB Output is correct
20 Correct 853 ms 10064 KB Output is correct
21 Execution timed out 2009 ms 23816 KB Time limit exceeded
22 Halted 0 ms 0 KB -