제출 #334762

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
334762		HoneyBadger	Snake Escaping (JOI18_snake_escaping)	C++17	75 / 100	2065 ms	25324 KiB

snake_escaping

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>
#include <algorithm>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <ctime>
#include <chrono>
 
 
 
#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")
 
 
 
#ifdef LOCAL
    #define dbg(x) cout << #x << " : " << x << endl;
#else
    #define dbg(x)
#endif
 
 
#define pb push_back
#define ppb pop_back()
#define mp make_pair
#define fi(a, b) for (int i = a; i < b; i++)
#define fj(a, b) for (int j = a; j < b; j++)
#define fk(a, b) for (int k = a; k < b; k++)
#define fi1(a, b) for (int i = a - 1; i >= b; i--)
#define fj1(a, b) for (int j = a - 1; j >= b; j--)
#define fk1(a, b) for (int k = a - 1; k >= b; k--)
#define fx(x, a) for (auto& x : a)
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define rep1(i, a, b) for (int i = a - 1; i >= b; --i)
#define siz(x) (int)x.size()
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
 
using namespace std;
 
template<typename T1, typename T2>inline void mine(T1 &x, const T2 &y) { if (y < x) x = y; }
template<typename T1, typename T2>inline void maxe(T1 &x, const T2 &y) { if (x < y) x = y; }
 
ostream& operator << (ostream &out, const vector<int> &b) {
    for (auto k : b) out << k << ' ';
    return out;
}
 
typedef long long ll;
typedef long double ld;
typedef char ch;
typedef string str;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<ch> vch;
typedef vector<vch> vvch;
typedef vector<str> vs;
 
 
 
const int MOD = 1000000007;
const int INF = 1000000050;
const long long BIG = (long long)2e18 + 50;
const int MX = 1 << 20;
const int PW = 20;
const double EPS = 1e-9;
 
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

inline int readChar();
inline int readInt();
inline void writeInt(int x, char end = 0);
inline void writeChar(int x);


static const int buf_size = 4096;

inline int getChar() {
    static char buf[buf_size];
    static int len = 0, pos = 0;
    if (pos == len)
        pos = 0, len = fread(buf, 1, buf_size, stdin);
    if (pos == len)
        return -1;
    return buf[pos++];
}

inline int readChar() {
    int c = getChar();
    while (c <= 32)
        c = getChar();
    return c;
}

inline int readInt() {
    int c = readChar();
    int x = 0;
    while ('0' <= c && c <= '9')
        x = x * 10 + c - '0', c = getChar();
    return x;
}


static int write_pos = 0;
static char write_buf[buf_size];

inline void writeChar(int x) {
    if (write_pos == buf_size)
        fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
    write_buf[write_pos++] = x;
}

inline void writeInt(int x, char end) {
    char s[9];
    int n = 0;
    while (x || !n)
        s[n++] = '0' + x % 10, x /= 10;
    while (n--)
        writeChar(s[n]);
    if (end)
        writeChar(end);
}


struct Flusher {
    ~Flusher() {
        if (write_pos)
            fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
    }
} flusher;


 
int n, q;
int a[MX];
int sos1[MX];
int sos0[MX];
int bits[MX];
 
void calc() {
    for (int mask = 0; mask < (1 << n); ++mask) {
        sos1[mask] = a[mask];
        sos0[mask] = a[mask];
        bits[mask] = bits[mask >> 1] + (mask & 1);
    }
    for (int i = 0; i < n; ++i) {
        for (int mask = 0; mask < (1 << n); ++mask) {
            if ((mask >> i) & 1) {
                sos1[mask] += sos1[mask ^ (1 << i)];
            } else {
                sos0[mask] += sos0[mask ^ (1 << i)];
            }
        }
    }
 
}
 
int ans;
str s;
 
 
void solveq(int i = 0, int mask = 0) {
    if (i == n) {
        ans += a[mask];
        return;
    }
    mask <<= 1;
    if (s[i] == '?') {
        solveq(i + 1, mask);
        solveq(i + 1, mask ^ 1);
    } else {
        solveq(i + 1, mask ^ (s[i] == '1'));
    }
}
 
void solve1(int i = 0, int mask = 0, int del = 0) {
    if (i == n) {
        if (del)
            ans -= sos1[mask];
        else
            ans += sos1[mask];
        return;
    }
    mask <<= 1;
    if (s[i] == '1') {
        solve1(i + 1, mask ^ 1, del);
        solve1(i + 1, mask, del ^ 1);  
    } else {
        solve1(i + 1, mask ^ (s[i] == '?'), del);
    }
}
 
void solve0(int i = 0, int mask = 0, int del = 0) {
    if (i == n) {
        if (del)
            ans -= sos0[mask];
        else
            ans += sos0[mask];
        return;
    }
    mask <<= 1;
    if (s[i] == '0') {
        solve0(i + 1, mask ^ 1, del ^ 1);
        solve0(i + 1, mask, del);
    } else {
        solve0(i + 1, mask ^ (s[i] != '?'), del);
    }
}
 
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    n = readInt(), q = readInt();
    for (int i = 0; i < (1 << n); ++i) {
        a[i] = readChar() - '0';
    }
 
    calc();
    s = string(n, '0');
    while (q--) {
        int pq = 0, p1 = 0, p0 = 0;
        fx(c, s) {
            c = readChar();
            pq += c == '?';
            p1 += c == '1';
            p0 += c == '0';
        }
        ans = 0;
        if (pq <= p1 && pq <= p0) {
            solveq();
        } else if (p1 <= pq && p1 <= p0) {
            solve1();
        } else {    
            solve0();
        }
        writeInt(ans, '\n');
    }
}

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