Submission #1098605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098605		Ejen	Snake Escaping (JOI18_snake_escaping)	C++17	0 / 100	1 ms	348 KiB

snake_escaping

#include <bits/stdc++.h>

#define el "\n"
#define fu(i, a, b) for (long long i = a; i <= b; ++i)
#define fd(i, a, b) for (long long i = a; i >= b; --i)
#define ff first
#define ss second
#define all(v) (v).begin(), (v).end()
#define sz(v) (ll)(v).size()
#define mask(i) (1LL << (i))
#define bit(x, i) ((x) >> (i) & 1)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

ll Rand(ll l, ll r) {
    return uniform_int_distribution<ll>(l, r) (rng);
}

ll last(ll msk)     {return msk & (-msk);}
ll pop_cnt(ll msk)  {return __builtin_popcountll(msk);}
ll ctz(ll msk)      {return __builtin_ctzll(msk);}
ll lg(ll msk)       {return 63 - __builtin_clzll(msk);}

template<class T1, class T2> bool minimize(T1 &a, T2 b) {
    return a > b ? a = b, 1 : 0;
}

template<class T1, class T2> bool maximize(T1 &a, T2 b) {
    return a < b ? a = b, 1 : 0;
}

template<class T> void print(T a) {
    for (auto x : a) cout << x << " ";
    cout << el;
}

template<class T> void compress(T &a) {
    sort(all(a));
    a.resize(unique(all(a)) - a.begin());
}

const long long N = 4e6 + 27, lim = 17, inf = 2e18, bl = 320, base = 311, mod = 1e9 + 7;

ll l, q;
ll s[N], f[N], dp[N];

signed main() {
    // freopen("CAU3.inp", "r", stdin);
    // freopen("CAU3.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> l >> q;
    fu(i, 0, mask(l) - 1) {
        char c;
        cin >> c;
        f[i] = dp[i] = s[i] = c - '0';
    }
    fu(i, 0, l - 1) fu(msk, 0, mask(l) - 1) {
        if (bit(msk, i)) f[msk] += f[msk ^ mask(i)];
        else dp[msk] += dp[msk ^ mask(i)];
    }
    while (q--) {
        string s;
        cin >> s;
        reverse(all(s));
        ll a = 0, b = 0, c = 0, res = 0;
        fu(i, 0, l - 1) {
            if (s[i] == '0') a += mask(i);
            else if (s[i] == '1') b += mask(i);
            else c += mask(i);
        }
        if (pop_cnt(a) <= pop_cnt(b) && pop_cnt(a) <= pop_cnt(c)) {
            fd(msk, a, 0) {
                msk &= a;
                if (pop_cnt(msk) & 1) res -= dp[msk | b];
                else res += dp[msk | b];
            }
        }
        else if (pop_cnt(b) <= pop_cnt(a) && pop_cnt(b) <= pop_cnt(c)) {
            fd(msk, b, 0) {
                msk &= b;
                if (pop_cnt(msk) & 1) res -= f[(b ^ msk) | c];
                else res += f[(b ^ msk) | c];
            }
        }
        else {
            fd(msk, c, 0) {
                msk &= c;
                res += s[msk | b];
            }
        }
        cout << res << el;
    }



}

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