oj.uz

Submission #591013

# Submission time Handle Problem Language Result Execution time Memory
591013 2022-07-06T17:47:16 Z piOOE Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 827 ms 44652 KB 
#include <bits/stdc++.h>

using namespace std;

const int L = 20;

int S[1 << L], A[1 << L], B[1 << L], popcnt[1 << L];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 1; i < 1 << L; ++i) {
        popcnt[i] = popcnt[i - (i & -i)] + 1;
    }
    int l, q;
    string s;
    cin >> l >> q >> s;
    for (int i = 0; i < 1 << l; ++i) {
        S[i] = A[i] = B[((1 << l) - 1) ^ i] = s[i] - '0';
    }
    for (int i = 0; i < l; ++i) {
        for (int mask = 0; mask < 1 << l; ++mask) {
            if (mask & 1 << i) {
                A[mask] += A[mask ^ 1 << i];
            }
        }
    }
    for (int i = 0; i < l; ++i) {
        for (int mask = 0; mask < 1 << l; ++mask) {
            if (mask & 1 << i) {
                B[mask] += B[mask ^ 1 << i];
            }
        }
    }
    while (q--) {
        string t;
        cin >> t;
        reverse(t.begin(), t.end());
        int mask0 = 0, mask1 = 0, mask2 = 0;
        for (int i = 0; i < l; ++i) {
            if (t[i] == '0') {
                mask0 ^= 1 << i;
            } else if (t[i] == '1') {
                mask1 ^= 1 << i;
            } else {
                mask2 ^= 1 << i;
            }
        }
        int ans = 0;
        if (popcnt[mask1] <= 6) {
            for (int mask = mask1; mask; mask = (mask - 1) & mask1) {
                ans += A[mask ^ mask2] * (popcnt[mask ^ mask1] & 1 ? -1 : 1);
            }
            ans += A[mask2] * (popcnt[mask1] & 1 ? -1 : 1);
        } else if (popcnt[mask0] <= 6) {
            for (int mask = mask0; mask; mask = (mask - 1) & mask0) {
                ans += B[mask ^ mask2] * (popcnt[mask ^ mask0] & 1 ? -1 : 1);
            }
            ans += B[mask2] * (popcnt[mask0] & 1 ? -1 : 1);
        } else {
            for (int mask = mask2; mask; mask = (mask - 1) & mask2) {
                ans += S[mask ^ mask1];
            }
            ans += S[mask1];
        }
        cout << ans << '\n';
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4436 KB Output is correct
2 Correct 3 ms 4372 KB Output is correct
3 Correct 4 ms 4436 KB Output is correct
4 Correct 3 ms 4480 KB Output is correct
5 Correct 3 ms 4436 KB Output is correct
6 Correct 3 ms 4376 KB Output is correct
7 Correct 3 ms 4436 KB Output is correct
8 Correct 5 ms 4440 KB Output is correct
9 Correct 4 ms 4428 KB Output is correct
10 Correct 3 ms 4436 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4436 KB Output is correct
2 Correct 3 ms 4372 KB Output is correct
3 Correct 4 ms 4436 KB Output is correct
4 Correct 3 ms 4480 KB Output is correct
5 Correct 3 ms 4436 KB Output is correct
6 Correct 3 ms 4376 KB Output is correct
7 Correct 3 ms 4436 KB Output is correct
8 Correct 5 ms 4440 KB Output is correct
9 Correct 4 ms 4428 KB Output is correct
10 Correct 3 ms 4436 KB Output is correct
11 Correct 281 ms 19148 KB Output is correct
12 Correct 202 ms 18792 KB Output is correct
13 Correct 276 ms 18084 KB Output is correct
14 Correct 219 ms 18276 KB Output is correct
15 Correct 253 ms 19180 KB Output is correct
16 Correct 284 ms 18400 KB Output is correct
17 Correct 253 ms 18264 KB Output is correct
18 Correct 160 ms 20172 KB Output is correct
19 Correct 270 ms 17132 KB Output is correct
20 Correct 258 ms 18860 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4436 KB Output is correct
2 Correct 3 ms 4372 KB Output is correct
3 Correct 4 ms 4436 KB Output is correct
4 Correct 3 ms 4480 KB Output is correct
5 Correct 3 ms 4436 KB Output is correct
6 Correct 3 ms 4376 KB Output is correct
7 Correct 3 ms 4436 KB Output is correct
8 Correct 5 ms 4440 KB Output is correct
9 Correct 4 ms 4428 KB Output is correct
10 Correct 3 ms 4436 KB Output is correct
11 Correct 281 ms 19148 KB Output is correct
12 Correct 202 ms 18792 KB Output is correct
13 Correct 276 ms 18084 KB Output is correct
14 Correct 219 ms 18276 KB Output is correct
15 Correct 253 ms 19180 KB Output is correct
16 Correct 284 ms 18400 KB Output is correct
17 Correct 253 ms 18264 KB Output is correct
18 Correct 160 ms 20172 KB Output is correct
19 Correct 270 ms 17132 KB Output is correct
20 Correct 258 ms 18860 KB Output is correct
21 Correct 370 ms 22144 KB Output is correct
22 Correct 227 ms 22372 KB Output is correct
23 Correct 297 ms 21328 KB Output is correct
24 Correct 273 ms 21212 KB Output is correct
25 Correct 242 ms 23220 KB Output is correct
26 Correct 313 ms 21704 KB Output is correct
27 Correct 315 ms 21660 KB Output is correct
28 Correct 181 ms 24160 KB Output is correct
29 Correct 328 ms 20236 KB Output is correct
30 Correct 273 ms 22380 KB Output is correct
31 Correct 297 ms 22212 KB Output is correct
32 Correct 279 ms 22216 KB Output is correct
33 Correct 231 ms 21040 KB Output is correct
34 Correct 301 ms 21196 KB Output is correct
35 Correct 319 ms 21584 KB Output is correct
36 Correct 182 ms 20236 KB Output is correct
37 Correct 223 ms 22204 KB Output is correct
38 Correct 311 ms 20200 KB Output is correct
39 Correct 336 ms 21396 KB Output is correct
40 Correct 321 ms 21184 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4436 KB Output is correct
2 Correct 3 ms 4372 KB Output is correct
3 Correct 4 ms 4436 KB Output is correct
4 Correct 3 ms 4480 KB Output is correct
5 Correct 3 ms 4436 KB Output is correct
6 Correct 3 ms 4376 KB Output is correct
7 Correct 3 ms 4436 KB Output is correct
8 Correct 5 ms 4440 KB Output is correct
9 Correct 4 ms 4428 KB Output is correct
10 Correct 3 ms 4436 KB Output is correct
11 Correct 66 ms 20172 KB Output is correct
12 Correct 63 ms 20192 KB Output is correct
13 Correct 104 ms 20136 KB Output is correct
14 Correct 75 ms 20040 KB Output is correct
15 Correct 64 ms 20172 KB Output is correct
16 Correct 81 ms 20036 KB Output is correct
17 Correct 82 ms 20032 KB Output is correct
18 Correct 82 ms 20304 KB Output is correct
19 Correct 97 ms 19960 KB Output is correct
20 Correct 70 ms 20176 KB Output is correct
21 Correct 70 ms 20156 KB Output is correct
22 Correct 74 ms 20044 KB Output is correct
23 Correct 65 ms 20052 KB Output is correct
24 Correct 86 ms 20036 KB Output is correct
25 Correct 78 ms 20036 KB Output is correct
26 Correct 61 ms 19912 KB Output is correct
27 Correct 65 ms 20168 KB Output is correct
28 Correct 68 ms 19976 KB Output is correct
29 Correct 101 ms 20044 KB Output is correct
30 Correct 72 ms 20100 KB Output is correct
31 Correct 65 ms 20076 KB Output is correct
32 Correct 78 ms 20056 KB Output is correct
33 Correct 83 ms 20036 KB Output is correct
34 Correct 60 ms 19952 KB Output is correct
35 Correct 79 ms 20068 KB Output is correct
36 Correct 75 ms 20040 KB Output is correct
37 Correct 75 ms 20052 KB Output is correct
38 Correct 96 ms 20080 KB Output is correct
39 Correct 80 ms 20104 KB Output is correct
40 Correct 76 ms 20040 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4436 KB Output is correct
2 Correct 3 ms 4372 KB Output is correct
3 Correct 4 ms 4436 KB Output is correct
4 Correct 3 ms 4480 KB Output is correct
5 Correct 3 ms 4436 KB Output is correct
6 Correct 3 ms 4376 KB Output is correct
7 Correct 3 ms 4436 KB Output is correct
8 Correct 5 ms 4440 KB Output is correct
9 Correct 4 ms 4428 KB Output is correct
10 Correct 3 ms 4436 KB Output is correct
11 Correct 281 ms 19148 KB Output is correct
12 Correct 202 ms 18792 KB Output is correct
13 Correct 276 ms 18084 KB Output is correct
14 Correct 219 ms 18276 KB Output is correct
15 Correct 253 ms 19180 KB Output is correct
16 Correct 284 ms 18400 KB Output is correct
17 Correct 253 ms 18264 KB Output is correct
18 Correct 160 ms 20172 KB Output is correct
19 Correct 270 ms 17132 KB Output is correct
20 Correct 258 ms 18860 KB Output is correct
21 Correct 370 ms 22144 KB Output is correct
22 Correct 227 ms 22372 KB Output is correct
23 Correct 297 ms 21328 KB Output is correct
24 Correct 273 ms 21212 KB Output is correct
25 Correct 242 ms 23220 KB Output is correct
26 Correct 313 ms 21704 KB Output is correct
27 Correct 315 ms 21660 KB Output is correct
28 Correct 181 ms 24160 KB Output is correct
29 Correct 328 ms 20236 KB Output is correct
30 Correct 273 ms 22380 KB Output is correct
31 Correct 297 ms 22212 KB Output is correct
32 Correct 279 ms 22216 KB Output is correct
33 Correct 231 ms 21040 KB Output is correct
34 Correct 301 ms 21196 KB Output is correct
35 Correct 319 ms 21584 KB Output is correct
36 Correct 182 ms 20236 KB Output is correct
37 Correct 223 ms 22204 KB Output is correct
38 Correct 311 ms 20200 KB Output is correct
39 Correct 336 ms 21396 KB Output is correct
40 Correct 321 ms 21184 KB Output is correct
41 Correct 66 ms 20172 KB Output is correct
42 Correct 63 ms 20192 KB Output is correct
43 Correct 104 ms 20136 KB Output is correct
44 Correct 75 ms 20040 KB Output is correct
45 Correct 64 ms 20172 KB Output is correct
46 Correct 81 ms 20036 KB Output is correct
47 Correct 82 ms 20032 KB Output is correct
48 Correct 82 ms 20304 KB Output is correct
49 Correct 97 ms 19960 KB Output is correct
50 Correct 70 ms 20176 KB Output is correct
51 Correct 70 ms 20156 KB Output is correct
52 Correct 74 ms 20044 KB Output is correct
53 Correct 65 ms 20052 KB Output is correct
54 Correct 86 ms 20036 KB Output is correct
55 Correct 78 ms 20036 KB Output is correct
56 Correct 61 ms 19912 KB Output is correct
57 Correct 65 ms 20168 KB Output is correct
58 Correct 68 ms 19976 KB Output is correct
59 Correct 101 ms 20044 KB Output is correct
60 Correct 72 ms 20100 KB Output is correct
61 Correct 65 ms 20076 KB Output is correct
62 Correct 78 ms 20056 KB Output is correct
63 Correct 83 ms 20036 KB Output is correct
64 Correct 60 ms 19952 KB Output is correct
65 Correct 79 ms 20068 KB Output is correct
66 Correct 75 ms 20040 KB Output is correct
67 Correct 75 ms 20052 KB Output is correct
68 Correct 96 ms 20080 KB Output is correct
69 Correct 80 ms 20104 KB Output is correct
70 Correct 76 ms 20040 KB Output is correct
71 Correct 410 ms 41632 KB Output is correct
72 Correct 405 ms 41776 KB Output is correct
73 Correct 543 ms 40452 KB Output is correct
74 Correct 725 ms 40656 KB Output is correct
75 Correct 408 ms 42604 KB Output is correct
76 Correct 773 ms 40932 KB Output is correct
77 Correct 827 ms 40828 KB Output is correct
78 Correct 276 ms 44652 KB Output is correct
79 Correct 403 ms 38748 KB Output is correct
80 Correct 440 ms 41772 KB Output is correct
81 Correct 563 ms 41592 KB Output is correct
82 Correct 608 ms 40664 KB Output is correct
83 Correct 421 ms 39808 KB Output is correct
84 Correct 773 ms 40520 KB Output is correct
85 Correct 729 ms 40704 KB Output is correct
86 Correct 264 ms 38596 KB Output is correct
87 Correct 395 ms 41516 KB Output is correct
88 Correct 462 ms 38604 KB Output is correct
89 Correct 540 ms 40328 KB Output is correct
90 Correct 558 ms 40648 KB Output is correct
91 Correct 476 ms 39796 KB Output is correct
92 Correct 625 ms 41068 KB Output is correct
93 Correct 717 ms 40772 KB Output is correct
94 Correct 275 ms 38656 KB Output is correct
95 Correct 659 ms 40792 KB Output is correct
96 Correct 642 ms 40892 KB Output is correct
97 Correct 645 ms 40616 KB Output is correct
98 Correct 653 ms 40740 KB Output is correct
99 Correct 660 ms 40604 KB Output is correct
100 Correct 637 ms 40760 KB Output is correct