oj.uz

Submission #415342

# Submission time Handle Problem Language Result Execution time Memory
415342 2021-06-01T00:23:52 Z meatrow Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 1970 ms 39220 KB 
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const int MOD = 1e9 + 7;

ll binpow(ll a, ll p, int mod = MOD) {
    ll res = 1;
    while (p) {
        if (p & 1) {
            (res *= a) %= mod;
        }
        p >>= 1;
        (a *= a) %= mod;
    }
    return res;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

const int LG = 20;
const int N = 1 << LG;

int zero[N], one[N];

void solve() {
    int l, q;
    cin >> l >> q;
    string s;
    cin >> s;
    int topkek = 1 << l;

    for (int mask = 0; mask < topkek; mask++) {
        zero[mask] = s[mask] - '0';
        one[mask] = s[mask ^ (topkek - 1)] - '0';
    }

    for (int i = 0; i < l; i++) {
        for (int mask = 0; mask < topkek; mask++) {
            if (mask >> i & 1) {
                zero[mask] += zero[mask ^ (1 << i)];
                one[mask] += one[mask ^ (1 << i)];
            }
        }
    }

    while (q--) {
        string query;
        cin >> query;
        vector<int> cnt(3);
        for (char c : query) {
            if (c == '?') {
                cnt[2]++;
            } else {
                cnt[c - '0']++;
            }
        }

        if (cnt[2] <= 6) {
            int ans = 0;
            int val = 0;
            vector<int> pos;
            for (int i = 0; i < l; i++) {
                val = val * 2;
                if (query[i] == '?') {
                    pos.push_back(l - i - 1);
                } else {
                    val += query[i] - '0';
                }
            }
            for (int mask = 0; mask < (1 << pos.size()); mask++) {
                int delta = 0;
                for (int i = 0; i < pos.size(); i++) {
                    if (mask >> i & 1) {
                        delta ^= 1 << pos[i];
                    }
                }
                ans += s[val ^ delta] - '0';
            }
            cout << ans << '\n';
            continue;
        }

        if (cnt[1] <= 6) {
            int ans = 0;
            int val = 0;
            vector<int> pos;
            for (int i = 0; i < l; i++) {
                if (query[i] == '1') {
                    pos.push_back(l - i - 1);
                }
                val = val * 2 + (query[i] != '0');
            }
            for (int mask = 0; mask < (1 << pos.size()); mask++) {
                int delta = 0;
                for (int i = 0; i < pos.size(); i++) {
                    if (mask >> i & 1) {
                        delta ^= 1 << pos[i];
                    }
                }
                if (__builtin_popcount(mask) & 1) {
                    ans -= zero[val ^ delta];
                } else {
                    ans += zero[val ^ delta];
                }
            }
            cout << ans << '\n';
            continue;
        }

        if (cnt[0] <= 6) {
            int ans = 0;
            int val = 0;
            vector<int> pos;
            for (int i = 0; i < l; i++) {
                if (query[i] == '0') {
                    pos.push_back(l - i - 1);
                }
                val = val * 2 + (query[i] != '1');
            }
            for (int mask = 0; mask < (1 << pos.size()); mask++) {
                int delta = 0;
                for (int i = 0; i < pos.size(); i++) {
                    if (mask >> i & 1) {
                        delta ^= 1 << pos[i];
                    }
                }
                if (__builtin_popcount(mask) & 1) {
                    ans -= one[val ^ delta];
                } else {
                    ans += one[val ^ delta];
                }
            }
            cout << ans << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        // cout << "Case #" << tc << ": ";
        solve();
    }
    return 0;
}

Compilation message

snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:80:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |                 for (int i = 0; i < pos.size(); i++) {
      |                                 ~~^~~~~~~~~~~~
snake_escaping.cpp:103:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |                 for (int i = 0; i < pos.size(); i++) {
      |                                 ~~^~~~~~~~~~~~
snake_escaping.cpp:130:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |                 for (int i = 0; i < pos.size(); i++) {
      |                                 ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 324 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 324 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 328 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 765 ms 15056 KB Output is correct
12 Correct 679 ms 14628 KB Output is correct
13 Correct 436 ms 14020 KB Output is correct
14 Correct 438 ms 14020 KB Output is correct
15 Correct 1057 ms 15112 KB Output is correct
16 Correct 565 ms 14200 KB Output is correct
17 Correct 546 ms 14120 KB Output is correct
18 Correct 265 ms 16052 KB Output is correct
19 Correct 252 ms 13124 KB Output is correct
20 Correct 706 ms 14724 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 324 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 324 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 328 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 765 ms 15056 KB Output is correct
12 Correct 679 ms 14628 KB Output is correct
13 Correct 436 ms 14020 KB Output is correct
14 Correct 438 ms 14020 KB Output is correct
15 Correct 1057 ms 15112 KB Output is correct
16 Correct 565 ms 14200 KB Output is correct
17 Correct 546 ms 14120 KB Output is correct
18 Correct 265 ms 16052 KB Output is correct
19 Correct 252 ms 13124 KB Output is correct
20 Correct 706 ms 14724 KB Output is correct
21 Correct 1375 ms 18128 KB Output is correct
22 Correct 630 ms 18244 KB Output is correct
23 Correct 584 ms 17296 KB Output is correct
24 Correct 560 ms 17088 KB Output is correct
25 Correct 494 ms 19104 KB Output is correct
26 Correct 716 ms 17572 KB Output is correct
27 Correct 702 ms 17448 KB Output is correct
28 Correct 280 ms 20052 KB Output is correct
29 Correct 275 ms 15996 KB Output is correct
30 Correct 1000 ms 18196 KB Output is correct
31 Correct 1139 ms 18072 KB Output is correct
32 Correct 779 ms 18056 KB Output is correct
33 Correct 464 ms 16904 KB Output is correct
34 Correct 585 ms 17020 KB Output is correct
35 Correct 688 ms 17432 KB Output is correct
36 Correct 268 ms 15968 KB Output is correct
37 Correct 1118 ms 18072 KB Output is correct
38 Correct 282 ms 16100 KB Output is correct
39 Correct 602 ms 17192 KB Output is correct
40 Correct 553 ms 17060 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 324 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 324 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 328 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 74 ms 11956 KB Output is correct
12 Correct 71 ms 11952 KB Output is correct
13 Correct 83 ms 11876 KB Output is correct
14 Correct 117 ms 11876 KB Output is correct
15 Correct 81 ms 12000 KB Output is correct
16 Correct 132 ms 11852 KB Output is correct
17 Correct 117 ms 11836 KB Output is correct
18 Correct 55 ms 12004 KB Output is correct
19 Correct 79 ms 11692 KB Output is correct
20 Correct 64 ms 11960 KB Output is correct
21 Correct 88 ms 11964 KB Output is correct
22 Correct 118 ms 11832 KB Output is correct
23 Correct 69 ms 11808 KB Output is correct
24 Correct 98 ms 11812 KB Output is correct
25 Correct 133 ms 11864 KB Output is correct
26 Correct 59 ms 11692 KB Output is correct
27 Correct 62 ms 11876 KB Output is correct
28 Correct 64 ms 11780 KB Output is correct
29 Correct 79 ms 11828 KB Output is correct
30 Correct 110 ms 11824 KB Output is correct
31 Correct 102 ms 11748 KB Output is correct
32 Correct 153 ms 12004 KB Output is correct
33 Correct 99 ms 11816 KB Output is correct
34 Correct 54 ms 11696 KB Output is correct
35 Correct 97 ms 11804 KB Output is correct
36 Correct 90 ms 11876 KB Output is correct
37 Correct 106 ms 11812 KB Output is correct
38 Correct 102 ms 11836 KB Output is correct
39 Correct 111 ms 11824 KB Output is correct
40 Correct 108 ms 11848 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 324 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 324 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 328 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 765 ms 15056 KB Output is correct
12 Correct 679 ms 14628 KB Output is correct
13 Correct 436 ms 14020 KB Output is correct
14 Correct 438 ms 14020 KB Output is correct
15 Correct 1057 ms 15112 KB Output is correct
16 Correct 565 ms 14200 KB Output is correct
17 Correct 546 ms 14120 KB Output is correct
18 Correct 265 ms 16052 KB Output is correct
19 Correct 252 ms 13124 KB Output is correct
20 Correct 706 ms 14724 KB Output is correct
21 Correct 1375 ms 18128 KB Output is correct
22 Correct 630 ms 18244 KB Output is correct
23 Correct 584 ms 17296 KB Output is correct
24 Correct 560 ms 17088 KB Output is correct
25 Correct 494 ms 19104 KB Output is correct
26 Correct 716 ms 17572 KB Output is correct
27 Correct 702 ms 17448 KB Output is correct
28 Correct 280 ms 20052 KB Output is correct
29 Correct 275 ms 15996 KB Output is correct
30 Correct 1000 ms 18196 KB Output is correct
31 Correct 1139 ms 18072 KB Output is correct
32 Correct 779 ms 18056 KB Output is correct
33 Correct 464 ms 16904 KB Output is correct
34 Correct 585 ms 17020 KB Output is correct
35 Correct 688 ms 17432 KB Output is correct
36 Correct 268 ms 15968 KB Output is correct
37 Correct 1118 ms 18072 KB Output is correct
38 Correct 282 ms 16100 KB Output is correct
39 Correct 602 ms 17192 KB Output is correct
40 Correct 553 ms 17060 KB Output is correct
41 Correct 74 ms 11956 KB Output is correct
42 Correct 71 ms 11952 KB Output is correct
43 Correct 83 ms 11876 KB Output is correct
44 Correct 117 ms 11876 KB Output is correct
45 Correct 81 ms 12000 KB Output is correct
46 Correct 132 ms 11852 KB Output is correct
47 Correct 117 ms 11836 KB Output is correct
48 Correct 55 ms 12004 KB Output is correct
49 Correct 79 ms 11692 KB Output is correct
50 Correct 64 ms 11960 KB Output is correct
51 Correct 88 ms 11964 KB Output is correct
52 Correct 118 ms 11832 KB Output is correct
53 Correct 69 ms 11808 KB Output is correct
54 Correct 98 ms 11812 KB Output is correct
55 Correct 133 ms 11864 KB Output is correct
56 Correct 59 ms 11692 KB Output is correct
57 Correct 62 ms 11876 KB Output is correct
58 Correct 64 ms 11780 KB Output is correct
59 Correct 79 ms 11828 KB Output is correct
60 Correct 110 ms 11824 KB Output is correct
61 Correct 102 ms 11748 KB Output is correct
62 Correct 153 ms 12004 KB Output is correct
63 Correct 99 ms 11816 KB Output is correct
64 Correct 54 ms 11696 KB Output is correct
65 Correct 97 ms 11804 KB Output is correct
66 Correct 90 ms 11876 KB Output is correct
67 Correct 106 ms 11812 KB Output is correct
68 Correct 102 ms 11836 KB Output is correct
69 Correct 111 ms 11824 KB Output is correct
70 Correct 108 ms 11848 KB Output is correct
71 Correct 555 ms 36124 KB Output is correct
72 Correct 568 ms 36340 KB Output is correct
73 Correct 1012 ms 34804 KB Output is correct
74 Correct 1970 ms 35176 KB Output is correct
75 Correct 883 ms 37352 KB Output is correct
76 Correct 1830 ms 35556 KB Output is correct
77 Correct 1576 ms 35456 KB Output is correct
78 Correct 394 ms 39220 KB Output is correct
79 Correct 412 ms 33096 KB Output is correct
80 Correct 768 ms 36524 KB Output is correct
81 Correct 1322 ms 36388 KB Output is correct
82 Correct 1936 ms 35308 KB Output is correct
83 Correct 793 ms 34400 KB Output is correct
84 Correct 1317 ms 35092 KB Output is correct
85 Correct 1463 ms 35348 KB Output is correct
86 Correct 406 ms 33168 KB Output is correct
87 Correct 548 ms 36180 KB Output is correct
88 Correct 451 ms 33100 KB Output is correct
89 Correct 1042 ms 34776 KB Output is correct
90 Correct 1414 ms 35168 KB Output is correct
91 Correct 794 ms 34488 KB Output is correct
92 Correct 1899 ms 35424 KB Output is correct
93 Correct 1663 ms 35332 KB Output is correct
94 Correct 396 ms 33200 KB Output is correct
95 Correct 1267 ms 35180 KB Output is correct
96 Correct 1219 ms 35596 KB Output is correct
97 Correct 1292 ms 35328 KB Output is correct
98 Correct 1251 ms 35392 KB Output is correct
99 Correct 1332 ms 35296 KB Output is correct
100 Correct 1191 ms 35232 KB Output is correct