oj.uz

Submission #522351

# Submission time Handle Problem Language Result Execution time Memory
522351 2022-02-04T16:17:27 Z Monarchuwu Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 748 ms 27492 KB 
#include<iostream>
#include<algorithm>
#include<string>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 1 << 20;
int l, q;
string s;

int pw[20 + 1], lg[N];
int a[N], f[N], g[N]; // f chứa con (1 = 01), g chứa cha (0 = 01)
void prep() {
    pw[0] = 1;
    for (int i = 1; i <= l; ++i) pw[i] = pw[i - 1] << 1;

    for (int msk = 0; msk < pw[l]; ++msk) {
        lg[msk] = lg[msk >> 1] + (msk & 1);
        a[msk] = f[msk] = g[msk] = s[msk] ^ 48;
    }

    for (int j = 0; j < l; ++j)
        for (int msk = 0; msk < pw[l]; ++msk)
            if (msk >> j & 1)
                f[msk] += f[msk ^ (1 << j)];
            else g[msk] += g[msk | (1 << j)];
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> l >> q >> s;
    prep();

    while (q--) {
        string t; cin >> t;
        int m0(0), m1(0), m2(0);
        for (char c : t) {
            m0 <<= 1, m1 <<= 1, m2 <<= 1;
            if (c == '0') ++m0;
            else if (c == '1') ++m1;
            else ++m2;
        }

        int ans(0), tmp = min({ lg[m0], lg[m1], lg[m2] });
        if (lg[m2] == tmp) { // brute ?
            for (int m = m2; true; m = (m - 1) & m2) {
                ans += a[m | m1];
                if (m == 0) break;
            }
        }
        else if (lg[m0] == tmp) { // inc-exc 0, dp sos 1 and ? => dùng g
            for (int m = m0; true; m = (m - 1) & m0) {
                if (lg[m] & 1)
                    ans -= g[m | m1];
                else ans += g[m | m1];
                if (m == 0) break;
            }
        }
        else { // inc-exc 1, dp sos 0 and ? => dùng f
            for (int m = m1, k = lg[m1] & 1; true; m = (m - 1) & m1) {
                if ((lg[m] & 1) == k)
                    ans += f[m | m2];
                else ans -= f[m | m2];
                if (m == 0) break;
            }
        }
        cout << ans << '\n';
    }
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 202 ms 8904 KB Output is correct
12 Correct 195 ms 8584 KB Output is correct
13 Correct 217 ms 7792 KB Output is correct
14 Correct 219 ms 8020 KB Output is correct
15 Correct 200 ms 9024 KB Output is correct
16 Correct 221 ms 8020 KB Output is correct
17 Correct 227 ms 8004 KB Output is correct
18 Correct 156 ms 9988 KB Output is correct
19 Correct 186 ms 6920 KB Output is correct
20 Correct 205 ms 8596 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 202 ms 8904 KB Output is correct
12 Correct 195 ms 8584 KB Output is correct
13 Correct 217 ms 7792 KB Output is correct
14 Correct 219 ms 8020 KB Output is correct
15 Correct 200 ms 9024 KB Output is correct
16 Correct 221 ms 8020 KB Output is correct
17 Correct 227 ms 8004 KB Output is correct
18 Correct 156 ms 9988 KB Output is correct
19 Correct 186 ms 6920 KB Output is correct
20 Correct 205 ms 8596 KB Output is correct
21 Correct 211 ms 9108 KB Output is correct
22 Correct 214 ms 7492 KB Output is correct
23 Correct 272 ms 6508 KB Output is correct
24 Correct 241 ms 6340 KB Output is correct
25 Correct 206 ms 8340 KB Output is correct
26 Correct 252 ms 6808 KB Output is correct
27 Correct 263 ms 6808 KB Output is correct
28 Correct 160 ms 9380 KB Output is correct
29 Correct 203 ms 5316 KB Output is correct
30 Correct 235 ms 7528 KB Output is correct
31 Correct 238 ms 7384 KB Output is correct
32 Correct 260 ms 7268 KB Output is correct
33 Correct 239 ms 6312 KB Output is correct
34 Correct 274 ms 6304 KB Output is correct
35 Correct 266 ms 6800 KB Output is correct
36 Correct 155 ms 5312 KB Output is correct
37 Correct 207 ms 7300 KB Output is correct
38 Correct 213 ms 5380 KB Output is correct
39 Correct 252 ms 6600 KB Output is correct
40 Correct 244 ms 6444 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 51 ms 19664 KB Output is correct
12 Correct 51 ms 19692 KB Output is correct
13 Correct 61 ms 19632 KB Output is correct
14 Correct 60 ms 19688 KB Output is correct
15 Correct 65 ms 19924 KB Output is correct
16 Correct 72 ms 19680 KB Output is correct
17 Correct 63 ms 19648 KB Output is correct
18 Correct 42 ms 19816 KB Output is correct
19 Correct 49 ms 19556 KB Output is correct
20 Correct 52 ms 19744 KB Output is correct
21 Correct 55 ms 19676 KB Output is correct
22 Correct 70 ms 19708 KB Output is correct
23 Correct 50 ms 19660 KB Output is correct
24 Correct 64 ms 19696 KB Output is correct
25 Correct 65 ms 19804 KB Output is correct
26 Correct 55 ms 19684 KB Output is correct
27 Correct 49 ms 19752 KB Output is correct
28 Correct 51 ms 19572 KB Output is correct
29 Correct 56 ms 19708 KB Output is correct
30 Correct 58 ms 19636 KB Output is correct
31 Correct 52 ms 19684 KB Output is correct
32 Correct 67 ms 19716 KB Output is correct
33 Correct 71 ms 19652 KB Output is correct
34 Correct 41 ms 19676 KB Output is correct
35 Correct 57 ms 19684 KB Output is correct
36 Correct 62 ms 19728 KB Output is correct
37 Correct 62 ms 19680 KB Output is correct
38 Correct 64 ms 19684 KB Output is correct
39 Correct 59 ms 19672 KB Output is correct
40 Correct 60 ms 19644 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 202 ms 8904 KB Output is correct
12 Correct 195 ms 8584 KB Output is correct
13 Correct 217 ms 7792 KB Output is correct
14 Correct 219 ms 8020 KB Output is correct
15 Correct 200 ms 9024 KB Output is correct
16 Correct 221 ms 8020 KB Output is correct
17 Correct 227 ms 8004 KB Output is correct
18 Correct 156 ms 9988 KB Output is correct
19 Correct 186 ms 6920 KB Output is correct
20 Correct 205 ms 8596 KB Output is correct
21 Correct 211 ms 9108 KB Output is correct
22 Correct 214 ms 7492 KB Output is correct
23 Correct 272 ms 6508 KB Output is correct
24 Correct 241 ms 6340 KB Output is correct
25 Correct 206 ms 8340 KB Output is correct
26 Correct 252 ms 6808 KB Output is correct
27 Correct 263 ms 6808 KB Output is correct
28 Correct 160 ms 9380 KB Output is correct
29 Correct 203 ms 5316 KB Output is correct
30 Correct 235 ms 7528 KB Output is correct
31 Correct 238 ms 7384 KB Output is correct
32 Correct 260 ms 7268 KB Output is correct
33 Correct 239 ms 6312 KB Output is correct
34 Correct 274 ms 6304 KB Output is correct
35 Correct 266 ms 6800 KB Output is correct
36 Correct 155 ms 5312 KB Output is correct
37 Correct 207 ms 7300 KB Output is correct
38 Correct 213 ms 5380 KB Output is correct
39 Correct 252 ms 6600 KB Output is correct
40 Correct 244 ms 6444 KB Output is correct
41 Correct 51 ms 19664 KB Output is correct
42 Correct 51 ms 19692 KB Output is correct
43 Correct 61 ms 19632 KB Output is correct
44 Correct 60 ms 19688 KB Output is correct
45 Correct 65 ms 19924 KB Output is correct
46 Correct 72 ms 19680 KB Output is correct
47 Correct 63 ms 19648 KB Output is correct
48 Correct 42 ms 19816 KB Output is correct
49 Correct 49 ms 19556 KB Output is correct
50 Correct 52 ms 19744 KB Output is correct
51 Correct 55 ms 19676 KB Output is correct
52 Correct 70 ms 19708 KB Output is correct
53 Correct 50 ms 19660 KB Output is correct
54 Correct 64 ms 19696 KB Output is correct
55 Correct 65 ms 19804 KB Output is correct
56 Correct 55 ms 19684 KB Output is correct
57 Correct 49 ms 19752 KB Output is correct
58 Correct 51 ms 19572 KB Output is correct
59 Correct 56 ms 19708 KB Output is correct
60 Correct 58 ms 19636 KB Output is correct
61 Correct 52 ms 19684 KB Output is correct
62 Correct 67 ms 19716 KB Output is correct
63 Correct 71 ms 19652 KB Output is correct
64 Correct 41 ms 19676 KB Output is correct
65 Correct 57 ms 19684 KB Output is correct
66 Correct 62 ms 19728 KB Output is correct
67 Correct 62 ms 19680 KB Output is correct
68 Correct 64 ms 19684 KB Output is correct
69 Correct 59 ms 19672 KB Output is correct
70 Correct 60 ms 19644 KB Output is correct
71 Correct 409 ms 26708 KB Output is correct
72 Correct 417 ms 24616 KB Output is correct
73 Correct 533 ms 23104 KB Output is correct
74 Correct 733 ms 23372 KB Output is correct
75 Correct 373 ms 25396 KB Output is correct
76 Correct 742 ms 23784 KB Output is correct
77 Correct 663 ms 23596 KB Output is correct
78 Correct 241 ms 27492 KB Output is correct
79 Correct 422 ms 21468 KB Output is correct
80 Correct 381 ms 24544 KB Output is correct
81 Correct 476 ms 24484 KB Output is correct
82 Correct 609 ms 23376 KB Output is correct
83 Correct 373 ms 22800 KB Output is correct
84 Correct 652 ms 23308 KB Output is correct
85 Correct 675 ms 23640 KB Output is correct
86 Correct 258 ms 21272 KB Output is correct
87 Correct 367 ms 24280 KB Output is correct
88 Correct 362 ms 21348 KB Output is correct
89 Correct 522 ms 23104 KB Output is correct
90 Correct 529 ms 23344 KB Output is correct
91 Correct 370 ms 22532 KB Output is correct
92 Correct 748 ms 23680 KB Output is correct
93 Correct 648 ms 23544 KB Output is correct
94 Correct 232 ms 21312 KB Output is correct
95 Correct 564 ms 23324 KB Output is correct
96 Correct 562 ms 23500 KB Output is correct
97 Correct 557 ms 23256 KB Output is correct
98 Correct 614 ms 23376 KB Output is correct
99 Correct 561 ms 23272 KB Output is correct
100 Correct 573 ms 23204 KB Output is correct