Submission #359107

#	Time	Username	Problem	Language	Result	Execution time	Memory
359107		cute_hater	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1509 ms	47608 KiB

snake_escaping

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>
#include <climits>
#include <stack>


/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")*/

using namespace std;

typedef long long ll;
typedef long double ld;

//#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define no {cout << "No"; return;}
#define yes {cout << "Yes"; return;}
#define mkp make_pair
#define mkt make_tuple
#define cerr if(0) cerr

const int N = 1100000;

int n, a[2][N], f[2][N];
bool odd[N];

void solveq(string & s) {
    int maskq = 0, masku = 0;
    loop(i, n) {
        if (s[i] == '?')
            maskq |= (1 << i);
        else if (s[i] == '1')
            masku |= (1 << i);
    }
    int ans = a[0][masku];
    for (int mask = maskq; mask; mask = (maskq & (mask - 1)))
        ans += a[0][mask | masku];
    cout << ans << "\n";
}

void solve01(string& s, bool fl) {
    int maskq = 0, masku = 0;
    loop(i, n) {
        if (s[i] == '?')
            maskq |= (1 << i);
        else if (s[i] == '1')
            masku |= (1 << i);
    }
    int ans = f[fl][maskq] * (odd[masku] ? -1 : 1);
    for (int mask = masku; mask; mask = (masku & (mask - 1)))
        ans += f[fl][mask | maskq] * (odd[mask] == odd[masku] ? 1 : -1);
    cout << ans << "\n";
}

void solve() {
    int q;
    cin >> n >> q;
    loop(i, (1 << n)) {
        char c; cin >> c;
        a[0][i] = f[0][i] = f[1][(1 << n) - 1 - i] = a[1][(1 << n) - i - 1] = c - '0';
    }
    loop(i, n)
        loop(mask, (1 << n))
            if (mask & (1 << i)) {
                f[0][mask] += f[0][mask ^ (1 << i)];
                f[1][mask] += f[1][mask ^ (1 << i)];
            }
    loop(mask, (1 << n))
        loop(i, n)
            if (mask & (1 << i))
                odd[mask] = !odd[mask ^ (1 << i)];
    loop(i, q) {
        string s; cin >> s;
        reverse(all(s));
        int cq = 0, c0 = 0, c1 = 0;
        loop(j, n)
            ++(s[j] == '?' ? cq : (s[j] == '0' ? c0 : c1));
        if (min({ cq, c1, c0 }) == cq)
            solveq(s);
        else if (min(c1, c0) == c1)
            solve01(s, 0);
        else {
            loop(j, n) {
                if (s[j] == '0')
                    s[j] = '1';
                else if (s[j] == '1')
                    s[j] = '0';
            }
            solve01(s, 1);
        }
    }
}

signed main() {
    //freopen("art2.in", "r", stdin);
    //freopen("art2.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //int t; cin >> t; loop(i, t)
    solve();
    return 0;
}

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