Submission #1204509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204509		spin	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	582 ms	30172 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
int n, q, And[1 << 21], Or[1 << 21];
string s;
int p[1 << 21];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>q;
    cin>>s;
    for(int i = 0; i < s.length(); i++)
    {
        And[i] = Or[i] = p[i] = s[i] - '0';
    }
    for(int i = 0; i < 21; i++)
    {
        for(int mask = 0; mask < (1 << 21); mask++)
        {
            if((mask >> i) & 1)Or[mask] += Or[mask - (1 << i)];
            else And[mask] += And[mask + (1 << i)];
        }
    }
    while(q--)
    {
        cin>>s;
        reverse(s.begin(), s.end());
        int mask1 = 0, mask0 = 0, maskq = 0;
        for(int i = 0; i < s.length(); i++)
        {
            if(s[i] == '1')mask1 += (1 << i);
            else if(s[i] == '0')mask0 += (1 << i);
            else if(s[i] == '?')maskq += (1 << i);
        }
        int ans = 0;
        if(__builtin_popcount(maskq) <= 6)
        {
            ans = p[mask1];
            for(int mask = maskq; mask > 0; mask = (mask - 1) & maskq)
            {
                ans += p[mask | mask1];
            }
        }
        else if(__builtin_popcount(mask1) <= 6)
        {
            ans = Or[maskq] * (__builtin_parity(mask1) ? -1 : 1);
            for(int mask = mask1; mask > 0; mask = (mask - 1) & mask1)
            {
                if(__builtin_parity(mask) ^ __builtin_parity(mask1))ans -= Or[mask | maskq];
                else ans += Or[mask | maskq];
            }
        }
        else if(__builtin_popcount(mask0) <= 6)
        {
            ans = And[mask1];
            for(int mask = mask0; mask > 0; mask = (mask - 1) & mask0)
            {
                if(__builtin_parity(mask))ans -= And[mask | mask1];
                else ans += And[mask | mask1];
            }
        }
        cout<<ans<<'\n';
    }
}
//let the dark calm you down.

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