Submission #704531

#	Time	Username	Problem	Language	Result	Execution time	Memory
704531		KenIsGenius	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1377 ms	39712 KiB

snake_escaping

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define ll long long
using namespace std;

#ifdef LOCAL
#define WOSAOJI freopen("in.txt", "r", stdin);
#else
#define WOSAOJI ios_base::sync_with_stdio(0), cin.tie(0);
#endif

#define chmax(a, b) (a) = (a) > (b) ? (a) : (b)
#define chmin(a, b) (a) = (a) < (b) ? (a) : (b)

// O(N*2^N + Q*N/3*2^(N/3) + QN)
// 4e8

int n, q;
string s;
vector<int> tmp;
int dp[1 << 20];
int dp0[1 << 20], dp1[1 << 20];

void solve1() {
    int x = 0;
    for (int i = 0; i < n; i++) {
        x *= 2; if (s[i] != '0') x++;
        if (s[i] == '1') tmp.pb(n - i - 1);
    }
    int ans = 0;
    for (int i = 0; i < 1 << tmp.size(); i++) {
        int now = x;
        for (int j = 0; j < tmp.size(); j++) {
            if (i >> j & 1) now -= 1 << tmp[j];
        }
        if (__builtin_parity(i)) ans -= dp1[now];
        else ans += dp1[now];
    }
    cout << ans << '\n';
}
void solve0() {
    int x = 0;
    for (int i = 0; i < n; i++) {
        x *= 2; if (s[i] == '1') x++;
        if (s[i] == '0') tmp.pb(n - i - 1);
    }
    int ans = 0;
    for (int i = 0; i < 1 << tmp.size(); i++) {
        int now = x;
        for (int j = 0; j < tmp.size(); j++) {
            if (i >> j & 1) now += 1 << tmp[j];
        }
        if (__builtin_parity(i)) ans -= dp0[now];
        else ans += dp0[now];
    }
    cout << ans << '\n';
}
void solveq() {
    int x = 0;
    for (int i = 0; i < n; i++) {
        x *= 2; if (s[i] == '1') x++;
        if (s[i] == '?') tmp.pb(n - i - 1);
    }
    int ans = 0;
    for (int i = 0; i < 1 << tmp.size(); i++) {
        int now = x;
        for (int j = 0; j < tmp.size(); j++) {
            if (i >> j & 1) now += 1 << tmp[j];
        }
        ans += dp[now];
    }
    cout << ans << '\n';
}

signed main() {
    WOSAOJI
    cin >> n >> q >> s;
    for (int i = 0; i < 1 << n; i++) {
        dp[i] = dp0[i] = dp1[i] = s[i] - '0';
    }
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < 1 << 20; i++) {
            if (i >> j & 1) {
                dp1[i] += dp1[i ^ (1 << j)];
            }
        }
        for (int i = (1 << 20) - 1; i >= 0; i--) {
            if (!(i >> j & 1)) {
                dp0[i] += dp0[i ^ (1 << j)];
            }
        }
    }
    while (q--) {
        tmp.clear();
        cin >> s;
        int zc = 0, oc = 0, qc = 0;
        for (char c : s) {
            if (c == '0') zc++;
            if (c == '1') oc++;
            if (c == '?') qc++;
        }
        if (oc <= zc and oc <= qc) {
            solve1();
        }
        else if (zc <= oc and zc <= qc) {
            solve0();
        }
        else {
            solveq();
        }
    }
}

Compilation message (stderr)

snake_escaping.cpp: In function 'void solve1()':
snake_escaping.cpp:36:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int j = 0; j < tmp.size(); j++) {
      |                         ~~^~~~~~~~~~~~
snake_escaping.cpp: In function 'void solve0()':
snake_escaping.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for (int j = 0; j < tmp.size(); j++) {
      |                         ~~^~~~~~~~~~~~
snake_escaping.cpp: In function 'void solveq()':
snake_escaping.cpp:70:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for (int j = 0; j < tmp.size(); j++) {
      |                         ~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25