oj.uz

Submission #702383

# Submission time Handle Problem Language Result Execution time Memory
702383 2023-02-23T20:47:12 Z bebra Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 2000 ms 23652 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 = 11;

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 1 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 376 KB Output is correct
8 Correct 0 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 1 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 376 KB Output is correct
8 Correct 0 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 214 ms 17232 KB Output is correct
12 Correct 194 ms 15816 KB Output is correct
13 Correct 230 ms 17620 KB Output is correct
14 Correct 216 ms 19660 KB Output is correct
15 Correct 229 ms 20316 KB Output is correct
16 Correct 267 ms 19356 KB Output is correct
17 Correct 262 ms 20152 KB Output is correct
18 Correct 146 ms 17212 KB Output is correct
19 Correct 202 ms 15236 KB Output is correct
20 Correct 245 ms 17632 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 1 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 376 KB Output is correct
8 Correct 0 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 214 ms 17232 KB Output is correct
12 Correct 194 ms 15816 KB Output is correct
13 Correct 230 ms 17620 KB Output is correct
14 Correct 216 ms 19660 KB Output is correct
15 Correct 229 ms 20316 KB Output is correct
16 Correct 267 ms 19356 KB Output is correct
17 Correct 262 ms 20152 KB Output is correct
18 Correct 146 ms 17212 KB Output is correct
19 Correct 202 ms 15236 KB Output is correct
20 Correct 245 ms 17632 KB Output is correct
21 Correct 359 ms 23652 KB Output is correct
22 Correct 208 ms 16428 KB Output is correct
23 Correct 544 ms 18992 KB Output is correct
24 Correct 310 ms 19596 KB Output is correct
25 Correct 436 ms 20548 KB Output is correct
26 Correct 683 ms 20844 KB Output is correct
27 Correct 698 ms 21196 KB Output is correct
28 Correct 166 ms 18400 KB Output is correct
29 Correct 322 ms 21612 KB Output is correct
30 Correct 735 ms 21904 KB Output is correct
31 Correct 576 ms 20112 KB Output is correct
32 Correct 324 ms 20268 KB Output is correct
33 Correct 297 ms 18724 KB Output is correct
34 Correct 672 ms 20204 KB Output is correct
35 Correct 719 ms 21196 KB Output is correct
36 Correct 155 ms 14240 KB Output is correct
37 Correct 199 ms 16172 KB Output is correct
38 Correct 706 ms 19872 KB Output is correct
39 Correct 361 ms 22780 KB Output is correct
40 Correct 336 ms 18764 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 1 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 376 KB Output is correct
8 Correct 0 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 207 ms 6508 KB Output is correct
12 Correct 38 ms 6780 KB Output is correct
13 Execution timed out 2082 ms 9228 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 1 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 376 KB Output is correct
8 Correct 0 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 214 ms 17232 KB Output is correct
12 Correct 194 ms 15816 KB Output is correct
13 Correct 230 ms 17620 KB Output is correct
14 Correct 216 ms 19660 KB Output is correct
15 Correct 229 ms 20316 KB Output is correct
16 Correct 267 ms 19356 KB Output is correct
17 Correct 262 ms 20152 KB Output is correct
18 Correct 146 ms 17212 KB Output is correct
19 Correct 202 ms 15236 KB Output is correct
20 Correct 245 ms 17632 KB Output is correct
21 Correct 359 ms 23652 KB Output is correct
22 Correct 208 ms 16428 KB Output is correct
23 Correct 544 ms 18992 KB Output is correct
24 Correct 310 ms 19596 KB Output is correct
25 Correct 436 ms 20548 KB Output is correct
26 Correct 683 ms 20844 KB Output is correct
27 Correct 698 ms 21196 KB Output is correct
28 Correct 166 ms 18400 KB Output is correct
29 Correct 322 ms 21612 KB Output is correct
30 Correct 735 ms 21904 KB Output is correct
31 Correct 576 ms 20112 KB Output is correct
32 Correct 324 ms 20268 KB Output is correct
33 Correct 297 ms 18724 KB Output is correct
34 Correct 672 ms 20204 KB Output is correct
35 Correct 719 ms 21196 KB Output is correct
36 Correct 155 ms 14240 KB Output is correct
37 Correct 199 ms 16172 KB Output is correct
38 Correct 706 ms 19872 KB Output is correct
39 Correct 361 ms 22780 KB Output is correct
40 Correct 336 ms 18764 KB Output is correct
41 Correct 207 ms 6508 KB Output is correct
42 Correct 38 ms 6780 KB Output is correct
43 Execution timed out 2082 ms 9228 KB Time limit exceeded
44 Halted 0 ms 0 KB -