Submission #971228

#	Time	Username	Problem	Language	Result	Execution time	Memory
971228		vyshniak_n	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1036 ms	55756 KiB

snake_escaping

//#pragma optimize("Ofast")
//#pragma optimize("unroll-loops")
//#pragma target("avx,avx2")

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>

typedef long long ll;
typedef long double ld;

using namespace std;

#define el '\n'
#define ff first
#define ss second
#define pb push_back
#define popb pop_back
#define point pair <ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

const ll N = 1e3 + 10;
const ll INF = 2e18 + 10;
const ll inf = 2e9 + 10;

void solve() {
    ll l, q;
    cin >> l >> q;

    string s;
    cin >> s;

    vector <ll> dpL(1 << l), dpR(1 << l), bits(1 << l);
    for (ll i = 0; i < (1 << l); i++)
        for (ll j = 0; j < l; j++)
            bits[i] += i >> j & 1;
    for (ll i = 0; i < (1 << l); i++)
        dpL[i] = s[i] - '0', dpR[i] = s[i] - '0';
    for (ll i = 0; i < l; i++)
        for (ll j = 0; j < (1 << l); j++)
            if (j >> i & 1)
                dpL[j] += dpL[j ^ (1 << i)];
    for (ll i = 0; i < l; i++)
        for (ll j = (1 << l) - 1; j >= 0; j--)
            if (j >> i & 1)
                dpR[j ^ (1 << i)] += dpR[j];

    while (q--) {
        string t;
        cin >> t;

        reverse(all(t));

        ll cnt1 = 0, cnt0 = 0, cnt = 0, res = 0;
        for (ll i = 0; i < l; i++) {
            if (t[i] == '1') cnt1++;
            else if (t[i] == '?') cnt++;
            else cnt0++;
        }

        ll mn = min({cnt1, cnt0, cnt});

        if (mn == cnt1) {
            ll mask = 0, c = 0;
            for (ll i = 0; i < l; i++) {
                if (t[i] == '?') c += 1 << i;
                else if (t[i] == '1') mask += 1 << i;
            }

            ll v = mask;

            if (bits[v | c] % 2 == 0) res += dpL[v | c];
            else res -= dpL[v | c];

            while (v > 0) {
                v = (v - 1) & mask;

                if (bits[v | c] % 2 == 0) res += dpL[v | c];
                else res -= dpL[v | c];
            }

            res = abs(res);
        } else if (mn == cnt) {
            ll mask = 0, c = 0;
            for (ll i = 0; i < l; i++) {
                if (t[i] == '?') mask += 1 << i;
                else if (t[i] == '1') c += 1 << i;
            }

            ll v = mask;
            res += s[v | c] - '0';

            while (v > 0) {
                v = (v - 1) & mask;
                res += s[v | c] - '0';
            }
        } else {
            ll mask = 0, c = 0;
            for (ll i = 0; i < l; i++) {
                if (t[i] == '1') c += 1 << i;
                else if (t[i] == '0') mask += 1 << i;
            }

            ll v = mask;

            if (bits[v | c] % 2 == 0) res += dpR[v | c];
            else res -= dpR[v | c];

            while (v > 0) {
                v = (v - 1) & mask;

                if (bits[v | c] % 2 == 0) res += dpR[v | c];
                else res -= dpR[v | c];
            }

            res = abs(res);
        }

        cout << res << el;
    }
    return;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int tests = 1;
    //cin >> tests;

    while (tests--)
        solve();
    return 0;
}

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