Submission #455178

#	Time	Username	Problem	Language	Result	Execution time	Memory
455178		Killer2501	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1333 ms	65536 KiB

snake_escaping

#include<bits/stdc++.h>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define pii pair<ll, pll>
using namespace std;
using ll = int;
const int  N = 2e6+55;
const ll mod = 1e9+7;
const ll mod1 = 1e9+1;
const ll base = 311;
const ll base1 = 331;
ll m, n, t, k, a[N], tong, b[N], dp[N], c[N], lab[N], cnt, ans, h[N], d[N];
priority_queue< pll, vector<pll>, greater<pll> > pq;
string s;
vector<ll> adj[N];
vector<pll> e;
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}


void f2(ll x)
{
    while(x)
    {
        cout << x % 2;
        x /= 2;
    }
    cout << '\n';
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> s;

    for(int i = 0; i < (1 << n); i ++)
    {
        a[i] = b[i] = c[i] = s[i] - '0';
    }
    for(int j = 0; j < n; j ++)
    {
        for(int i = 0; i < (1<<n); i ++)
        {
            if((i >> j) & 1)b[i] += b[i^(1<<j)];
            else a[i] += a[i^(1<<j)];
        }
    }
    //cout << b[0] << '\n';
    while(m -- > 0)
    {
        cin >> s;
        reverse(s.begin(), s.end());
        ll c0 = 0, c1 = 0, c2 = 0;
        for(int i = 0; i < n; i ++)
        {
            if(s[i] == '0')++c0;
            else if(s[i] == '1')++c1;
            else ++c2;
        }
        ll x = 0, y = 0;
        ans = 0;
        if(c0 == min(min(c0, c1), c2))
        {
            for(int i = 0; i < n; i ++)
            {
                if(s[i] == '0')x |= (1<<i);
                if(s[i] == '1')y |= (1<<i);
            }
            for(int i = x; ; i = (i - 1) & x)
            {
                if(__builtin_popcount(i) & 1)ans -= a[i+y];
                else ans += a[i+y];
                if(!i)break;
            }
        }
        else if(c1 == min(min(c0, c1), c2))
        {
            for(int i = 0; i < n; i ++)
            {
                if(s[i] == '1')x |= (1<<i);
                if(s[i] != '0')y |= (1<<i);
            }
            //cout << x <<" "<< y << '\n';
            for(int i = x; ; i = (i - 1) & x)
            {
                if(__builtin_popcount(i) & 1)ans -= b[y-i];
                else ans += b[y-i];
                if(!i)break;
            }

        }
        else
        {
            for(int i = 0; i < n; i ++)
            {
                if(s[i] == '?')x |= (1<<i);
                if(s[i] == '1')y |= (1<<i);
            }
            for(int i = x; ; i = (i - 1) & x)
            {
                ans += c[i+y];
                if(!i)break;
            }
        }
        cout << ans << '\n';
    }
}
/*
3 5
12345678
000
0??
1?0
?11
???
*/

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