oj.uz

Submission #897364

# Submission time Handle Problem Language Result Execution time Memory
897364 2024-01-03T02:17:08 Z box Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 490 ms 43484 KB 
#include <bits/stdc++.h>
using namespace std;
    
const int L = 20, N = 1 << L;
    
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int l, q; cin >> l >> q;
    string s; cin >> s;
    int n = 1 << l;
    static int f[N], g[N], c[N];
    for (int i = 0; i < n; i++)
        f[i] += s[i] - '0', g[i] += s[i] - '0';
    for (int i = 1; i < n; i++)
        c[i] = c[i & (i - 1)] + 1;
    for (int b = 0; b < l; b++)
        for (int i = 0; i < n; i++)
            if (i >> b & 1) {
                f[i] += f[i ^ (1 << b)];
                g[i ^ (1 << b)] += g[i];
            }
    while (q--) {
        string t; cin >> t;
        reverse(t.begin(), t.end());
        int i0 = 0, i1 = 0, iq = 0;
        for (int b = 0; b < l; b++)
            if (t[b] == '0') i0 |= 1 << b;
            else if (t[b] == '1') i1 |= 1 << b;
            else iq |= 1 << b;
        int v = 0;
        if (c[iq] <= 7) {
            for (int t = iq; ; t = (t - 1) & iq) {
                v += s[t | i1] - '0';
                if (t == 0) break;
            }
        } else if (c[i0] <= 7) {
            for (int t = i0; ; t = (t - 1) & i0) {
                v += (c[t] % 2 ? -1 : +1) * g[t | i1];
                if (t == 0) break;
            }
        } else {
            for (int t = i1; ; t = (t - 1) & i1) {
                v += (c[t] % 2 ? -1 : +1) * f[(t ^ i1) | iq];
                if (t == 0) break;
            }
        }
        cout << v << '\n';
    }
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4572 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 203 ms 19284 KB Output is correct
12 Correct 222 ms 18936 KB Output is correct
13 Correct 208 ms 18184 KB Output is correct
14 Correct 203 ms 18068 KB Output is correct
15 Correct 245 ms 19156 KB Output is correct
16 Correct 221 ms 18320 KB Output is correct
17 Correct 238 ms 18280 KB Output is correct
18 Correct 137 ms 20084 KB Output is correct
19 Correct 168 ms 17140 KB Output is correct
20 Correct 223 ms 18784 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4572 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 203 ms 19284 KB Output is correct
12 Correct 222 ms 18936 KB Output is correct
13 Correct 208 ms 18184 KB Output is correct
14 Correct 203 ms 18068 KB Output is correct
15 Correct 245 ms 19156 KB Output is correct
16 Correct 221 ms 18320 KB Output is correct
17 Correct 238 ms 18280 KB Output is correct
18 Correct 137 ms 20084 KB Output is correct
19 Correct 168 ms 17140 KB Output is correct
20 Correct 223 ms 18784 KB Output is correct
21 Correct 338 ms 22240 KB Output is correct
22 Correct 266 ms 22488 KB Output is correct
23 Correct 242 ms 21344 KB Output is correct
24 Correct 238 ms 21076 KB Output is correct
25 Correct 229 ms 23120 KB Output is correct
26 Correct 259 ms 21808 KB Output is correct
27 Correct 259 ms 21584 KB Output is correct
28 Correct 155 ms 24432 KB Output is correct
29 Correct 192 ms 20128 KB Output is correct
30 Correct 266 ms 22528 KB Output is correct
31 Correct 284 ms 22064 KB Output is correct
32 Correct 246 ms 22360 KB Output is correct
33 Correct 210 ms 21072 KB Output is correct
34 Correct 275 ms 21060 KB Output is correct
35 Correct 263 ms 21564 KB Output is correct
36 Correct 163 ms 20352 KB Output is correct
37 Correct 259 ms 22252 KB Output is correct
38 Correct 195 ms 20048 KB Output is correct
39 Correct 236 ms 21436 KB Output is correct
40 Correct 236 ms 21072 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4572 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 40 ms 16116 KB Output is correct
12 Correct 46 ms 16212 KB Output is correct
13 Correct 48 ms 15900 KB Output is correct
14 Correct 50 ms 15944 KB Output is correct
15 Correct 42 ms 16196 KB Output is correct
16 Correct 46 ms 16112 KB Output is correct
17 Correct 52 ms 15956 KB Output is correct
18 Correct 38 ms 16216 KB Output is correct
19 Correct 47 ms 15872 KB Output is correct
20 Correct 43 ms 16220 KB Output is correct
21 Correct 47 ms 16212 KB Output is correct
22 Correct 49 ms 15944 KB Output is correct
23 Correct 42 ms 15960 KB Output is correct
24 Correct 49 ms 16368 KB Output is correct
25 Correct 52 ms 16116 KB Output is correct
26 Correct 45 ms 15956 KB Output is correct
27 Correct 45 ms 17140 KB Output is correct
28 Correct 44 ms 15940 KB Output is correct
29 Correct 47 ms 15952 KB Output is correct
30 Correct 46 ms 16116 KB Output is correct
31 Correct 45 ms 16116 KB Output is correct
32 Correct 49 ms 16112 KB Output is correct
33 Correct 55 ms 16112 KB Output is correct
34 Correct 39 ms 15860 KB Output is correct
35 Correct 52 ms 15956 KB Output is correct
36 Correct 51 ms 16184 KB Output is correct
37 Correct 47 ms 16112 KB Output is correct
38 Correct 50 ms 16112 KB Output is correct
39 Correct 48 ms 15928 KB Output is correct
40 Correct 47 ms 16116 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4572 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 203 ms 19284 KB Output is correct
12 Correct 222 ms 18936 KB Output is correct
13 Correct 208 ms 18184 KB Output is correct
14 Correct 203 ms 18068 KB Output is correct
15 Correct 245 ms 19156 KB Output is correct
16 Correct 221 ms 18320 KB Output is correct
17 Correct 238 ms 18280 KB Output is correct
18 Correct 137 ms 20084 KB Output is correct
19 Correct 168 ms 17140 KB Output is correct
20 Correct 223 ms 18784 KB Output is correct
21 Correct 338 ms 22240 KB Output is correct
22 Correct 266 ms 22488 KB Output is correct
23 Correct 242 ms 21344 KB Output is correct
24 Correct 238 ms 21076 KB Output is correct
25 Correct 229 ms 23120 KB Output is correct
26 Correct 259 ms 21808 KB Output is correct
27 Correct 259 ms 21584 KB Output is correct
28 Correct 155 ms 24432 KB Output is correct
29 Correct 192 ms 20128 KB Output is correct
30 Correct 266 ms 22528 KB Output is correct
31 Correct 284 ms 22064 KB Output is correct
32 Correct 246 ms 22360 KB Output is correct
33 Correct 210 ms 21072 KB Output is correct
34 Correct 275 ms 21060 KB Output is correct
35 Correct 263 ms 21564 KB Output is correct
36 Correct 163 ms 20352 KB Output is correct
37 Correct 259 ms 22252 KB Output is correct
38 Correct 195 ms 20048 KB Output is correct
39 Correct 236 ms 21436 KB Output is correct
40 Correct 236 ms 21072 KB Output is correct
41 Correct 40 ms 16116 KB Output is correct
42 Correct 46 ms 16212 KB Output is correct
43 Correct 48 ms 15900 KB Output is correct
44 Correct 50 ms 15944 KB Output is correct
45 Correct 42 ms 16196 KB Output is correct
46 Correct 46 ms 16112 KB Output is correct
47 Correct 52 ms 15956 KB Output is correct
48 Correct 38 ms 16216 KB Output is correct
49 Correct 47 ms 15872 KB Output is correct
50 Correct 43 ms 16220 KB Output is correct
51 Correct 47 ms 16212 KB Output is correct
52 Correct 49 ms 15944 KB Output is correct
53 Correct 42 ms 15960 KB Output is correct
54 Correct 49 ms 16368 KB Output is correct
55 Correct 52 ms 16116 KB Output is correct
56 Correct 45 ms 15956 KB Output is correct
57 Correct 45 ms 17140 KB Output is correct
58 Correct 44 ms 15940 KB Output is correct
59 Correct 47 ms 15952 KB Output is correct
60 Correct 46 ms 16116 KB Output is correct
61 Correct 45 ms 16116 KB Output is correct
62 Correct 49 ms 16112 KB Output is correct
63 Correct 55 ms 16112 KB Output is correct
64 Correct 39 ms 15860 KB Output is correct
65 Correct 52 ms 15956 KB Output is correct
66 Correct 51 ms 16184 KB Output is correct
67 Correct 47 ms 16112 KB Output is correct
68 Correct 50 ms 16112 KB Output is correct
69 Correct 48 ms 15928 KB Output is correct
70 Correct 47 ms 16116 KB Output is correct
71 Correct 341 ms 40320 KB Output is correct
72 Correct 392 ms 40436 KB Output is correct
73 Correct 393 ms 39120 KB Output is correct
74 Correct 487 ms 39360 KB Output is correct
75 Correct 337 ms 41440 KB Output is correct
76 Correct 490 ms 39544 KB Output is correct
77 Correct 454 ms 39656 KB Output is correct
78 Correct 235 ms 43484 KB Output is correct
79 Correct 314 ms 37304 KB Output is correct
80 Correct 347 ms 40592 KB Output is correct
81 Correct 457 ms 40552 KB Output is correct
82 Correct 490 ms 39416 KB Output is correct
83 Correct 320 ms 38484 KB Output is correct
84 Correct 419 ms 39388 KB Output is correct
85 Correct 486 ms 39496 KB Output is correct
86 Correct 224 ms 37360 KB Output is correct
87 Correct 308 ms 40520 KB Output is correct
88 Correct 304 ms 37368 KB Output is correct
89 Correct 380 ms 39412 KB Output is correct
90 Correct 414 ms 39336 KB Output is correct
91 Correct 332 ms 38644 KB Output is correct
92 Correct 454 ms 39672 KB Output is correct
93 Correct 443 ms 39608 KB Output is correct
94 Correct 211 ms 37384 KB Output is correct
95 Correct 394 ms 39420 KB Output is correct
96 Correct 399 ms 39508 KB Output is correct
97 Correct 418 ms 39524 KB Output is correct
98 Correct 397 ms 39500 KB Output is correct
99 Correct 434 ms 39416 KB Output is correct
100 Correct 457 ms 39316 KB Output is correct