oj.uz

Submission #702384

# Submission time Handle Problem Language Result Execution time Memory
702384 2023-02-23T20:48:05 Z bebra Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 2000 ms 23616 KB 
#include <bits/stdc++.h>
using namespace std;

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


constexpr int MAX_Q = 1e6 + 5;
constexpr int MAX_BIT = 20;
constexpr int MAX_N = 1 << 20;
constexpr int MAGIC = 9;

int ans[MAX_Q];
int dp[MAX_N];

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

    int k, q;
    cin >> k >> q;

    string s;
    cin >> s;

    map<int, vector<pair<int, int>>> shifts;
    for (int j = 0; j < q; ++j) {
        string t;
        cin >> t;
        reverse(t.begin(), t.end());

        int mask = 0;
        int shift = 0;
        int bits_cnt = 0;
        for (int i = 0; i < k; ++i) {
            if (t[i] == '?') {
                mask |= 1 << i;
                ++bits_cnt;
            } else if (t[i] == '1') {
                shift |= 1 << i;
            }
        }
        shifts[shift].emplace_back(mask, j);
    }

    int n = 1 << k;
    for (const auto& [shift, values] : shifts) {

        if (values.size() >= MAGIC) {
            for (int mask = 0; (mask | shift) < n; ++mask) {
                if ((mask & shift) == 0) {
                    dp[mask] = s[mask | shift] - '0';
                }
            }

            for (int bit = 0; bit < k; ++bit) {
                if (shift & (1 << bit)) continue;

                for (int mask = 0; (mask | shift) < n; ++mask) {
                    if ((mask & shift) != 0) continue;

                    if (mask & (1 << bit)) {
                        dp[mask] += dp[mask ^ (1 << bit)];
                    }
                }
            }

            for (const auto& [mask, idx] : values) {
                ans[idx] = dp[mask];
            }

            for (int mask = 0; (mask | shift) < n; ++mask) {
                dp[mask] = 0;
            }
        } else {
            for (const auto& [mask, idx] : values) {
                ans[idx] = s[shift] - '0';
                for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
                    ans[idx] += s[submask | shift] - '0';
                }
            }
        }
    }

    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }
    
    return 0;
}


/*
4
1
3141592653589793
?01?


*/

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 208 ms 17320 KB Output is correct
12 Correct 194 ms 15860 KB Output is correct
13 Correct 231 ms 17524 KB Output is correct
14 Correct 211 ms 19680 KB Output is correct
15 Correct 223 ms 20240 KB Output is correct
16 Correct 253 ms 19320 KB Output is correct
17 Correct 255 ms 19948 KB Output is correct
18 Correct 144 ms 17184 KB Output is correct
19 Correct 188 ms 15252 KB Output is correct
20 Correct 265 ms 17600 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 208 ms 17320 KB Output is correct
12 Correct 194 ms 15860 KB Output is correct
13 Correct 231 ms 17524 KB Output is correct
14 Correct 211 ms 19680 KB Output is correct
15 Correct 223 ms 20240 KB Output is correct
16 Correct 253 ms 19320 KB Output is correct
17 Correct 255 ms 19948 KB Output is correct
18 Correct 144 ms 17184 KB Output is correct
19 Correct 188 ms 15252 KB Output is correct
20 Correct 265 ms 17600 KB Output is correct
21 Correct 355 ms 23616 KB Output is correct
22 Correct 212 ms 16404 KB Output is correct
23 Correct 545 ms 19020 KB Output is correct
24 Correct 294 ms 19660 KB Output is correct
25 Correct 434 ms 20680 KB Output is correct
26 Correct 690 ms 20848 KB Output is correct
27 Correct 715 ms 21288 KB Output is correct
28 Correct 163 ms 18164 KB Output is correct
29 Correct 316 ms 21584 KB Output is correct
30 Correct 765 ms 21864 KB Output is correct
31 Correct 571 ms 20360 KB Output is correct
32 Correct 315 ms 20276 KB Output is correct
33 Correct 291 ms 18688 KB Output is correct
34 Correct 678 ms 20168 KB Output is correct
35 Correct 708 ms 21324 KB Output is correct
36 Correct 153 ms 14292 KB Output is correct
37 Correct 198 ms 16224 KB Output is correct
38 Correct 705 ms 19916 KB Output is correct
39 Correct 373 ms 22808 KB Output is correct
40 Correct 337 ms 18716 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 202 ms 6504 KB Output is correct
12 Correct 38 ms 6776 KB Output is correct
13 Execution timed out 2085 ms 9156 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 208 ms 17320 KB Output is correct
12 Correct 194 ms 15860 KB Output is correct
13 Correct 231 ms 17524 KB Output is correct
14 Correct 211 ms 19680 KB Output is correct
15 Correct 223 ms 20240 KB Output is correct
16 Correct 253 ms 19320 KB Output is correct
17 Correct 255 ms 19948 KB Output is correct
18 Correct 144 ms 17184 KB Output is correct
19 Correct 188 ms 15252 KB Output is correct
20 Correct 265 ms 17600 KB Output is correct
21 Correct 355 ms 23616 KB Output is correct
22 Correct 212 ms 16404 KB Output is correct
23 Correct 545 ms 19020 KB Output is correct
24 Correct 294 ms 19660 KB Output is correct
25 Correct 434 ms 20680 KB Output is correct
26 Correct 690 ms 20848 KB Output is correct
27 Correct 715 ms 21288 KB Output is correct
28 Correct 163 ms 18164 KB Output is correct
29 Correct 316 ms 21584 KB Output is correct
30 Correct 765 ms 21864 KB Output is correct
31 Correct 571 ms 20360 KB Output is correct
32 Correct 315 ms 20276 KB Output is correct
33 Correct 291 ms 18688 KB Output is correct
34 Correct 678 ms 20168 KB Output is correct
35 Correct 708 ms 21324 KB Output is correct
36 Correct 153 ms 14292 KB Output is correct
37 Correct 198 ms 16224 KB Output is correct
38 Correct 705 ms 19916 KB Output is correct
39 Correct 373 ms 22808 KB Output is correct
40 Correct 337 ms 18716 KB Output is correct
41 Correct 202 ms 6504 KB Output is correct
42 Correct 38 ms 6776 KB Output is correct
43 Execution timed out 2085 ms 9156 KB Time limit exceeded
44 Halted 0 ms 0 KB -