Submission #415342

#	Time	Username	Problem	Language	Result	Execution time	Memory
415342		meatrow	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1970 ms	39220 KiB

snake_escaping

// #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 (stderr)

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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25