Submission #1001205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001205		mispertion	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	874 ms	46064 KiB

snake_escaping

#include<bits/stdc++.h>
 
using namespace std;
 
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;
 
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"
 
const ld PI = 3.1415926535;
const int N = 2e6+10;
const int M = 7e6 + 1;
int mod = 1e9+7;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;
const int P = 2;
 
int mult(int a, int b) {
    return a * 1LL * b % mod;
}
 
int sum(int a, int b) { 
    if (a + b < 0)
        return a + b + mod;
    if (a + b >= mod)
        return a + b - mod;
    return a + b;
}
 
ll binpow(ll a, ll n) {
    if (n == 0)
        return 1;
    if (n % 2 == 1) {
        return binpow(a, n - 1) * a % mod;
    } else {
        ll b = binpow(a, n / 2);
        return b * b % mod;
    }
}
 
int n, q, a[N], sos[N], sou[N];

void solve(){
    cin >> n >> q;
    string tmp;
    cin >> tmp;
    for(int i = 0; i < (1 << n); i++)
        sos[i] = sou[i] = a[i] = tmp[i] - '0';
    //sum over subsets
    for(int i = 0; i < n; i++)
        for(int mask = 0; mask < (1 << n); mask++)
            if(mask & (1 << i))
                sos[mask] += sos[mask ^ (1 << i)];
    for(int i = 0; i < n; i++)
        for(int mask = (1 << n) - 1; mask >= 0; mask--)
            if(!(mask & (1 << i)))
                sou[mask] += sou[mask ^ (1 << i)];
    while(q--){
        vector<int> und = {}, zer = {}, one = {};
        string s;
        cin >> s;
        reverse(all(s));
        int mainm = 0, unmask = 0, zermask = 0;
        for(int i = 0; i < sz(s); i++){
            if(s[i] == '?')
                und.pb(i), unmask += (1 << i);
            if(s[i] == '0')
                zer.pb(i), zermask += (1 << i);
            if(s[i] == '1')
                one.pb(i), mainm += (1 << i);
        }
        if(sz(und) <= sz(zer) && sz(und) <= sz(one)){
            int ans = a[mainm];
            for(int mask = unmask; mask > 0; mask = (mask - 1) & unmask){
                ans += a[mask + mainm];
            }
            cout << ans << '\n';
        }else if(sz(zer) <= sz(und) && sz(one) >= sz(zer)){
            int ans = sou[mainm];
            for(int mask = zermask; mask > 0; mask = (mask - 1) & zermask){
                int cnt = __builtin_popcount(mask);
                if(cnt % 2)
                    ans -= sou[mask + mainm];
                else
                    ans += sou[mask + mainm];
            }
            cout << ans << '\n';
        }else{
            int ans = 0;
            if(sz(one) % 2)
                ans -= sos[unmask];
            else
                ans += sos[unmask];
            for(int mask = mainm; mask > 0; mask = (mask - 1) & mainm){
                int cnt = sz(one) - __builtin_popcount(mask);
                if(cnt % 2)
                    ans -= sos[mask + unmask];
                else
                    ans += sos[mask + unmask];
            }
            cout << ans << '\n';
        }
    }
}
 
signed main() {
    mispertion;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

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