Submission #391450

#	Time	Username	Problem	Language	Result	Execution time	Memory
391450		iANikzad	Snake Escaping (JOI18_snake_escaping)	C++14	65 / 100	2040 ms	10996 KiB

snake_escaping

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second
#define debug(x) cerr<<#x<<" :"<<x<<"\n"
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define FAST ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
//#define int long long

typedef long long ll;
typedef long double ld;

const int maxn = 20;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const int mlog = 20;
const int SQ = 400;

int sos[1 << 20], rsos[1 << 20];

string s, k;
int l, q;
int a, b, c;

int32_t main()
{
    FAST;

    cin >> l >> q >> s;

    for(int i = 0; i < (1 << l); i++)
        sos[i] = s[i] - '0', rsos[i] = s[(1 << l) - i - 1] - '0';

    for(int i = 0; i < l; i++) 
        for(int mask = 0; mask < (1 << l); mask++)
            if(mask & (1 << i))
                sos[mask] += sos[mask ^ (1 << i)], rsos[mask] += rsos[mask ^ (1 << i)];

    while(q--)
    {
        cin >> k;
        reverse(all(k));

        a = b = c = 0;
        int ans = 0, base = 0, mask = 0;

        for(int i = 0; i < l; i++)
        {
            if(k[i] == '?') a++;
            if(k[i] == '0') b++;
            if(k[i] == '1') c++;
        }

        if(a < 7)
        {
            for(int i = 0; i < l; i++)
            {
                if (k[i] == '?') mask += 1 << i;
                else if (k[i] == '1') base += 1 << i;
            }

            for (int i = mask; i; i = mask & (i - 1)) ans += s[i | base] - '0';
            ans += s[base] - '0';
        }
        else if(b < 7)
        {
            for(int i = 0; i < l; i++)
            {
                if (k[i] == '0') mask += 1 << i;
                else if (k[i] == '?') base += 1 << i;
            }

            for (int i = mask; i; i = mask & (i - 1)) ans += ((b - __builtin_popcount(i)) & 1 ? -1 : 1) * rsos[i | base];
            ans += (b & 1 ? -1 : 1) * rsos[base];
         
        }
        else
        {
            for(int i = 0; i < l; i++)
            {
                if (k[i] == '1') mask += 1 << i;
                else if (k[i] == '?') base += 1 << i;
            }

            for (int i = mask; i; i = mask & (i - 1)) ans += ((c - __builtin_popcount(i)) & 1 ? -1 : 1) * sos[i | base];
            ans += (c & 1 ? -1 : 1) * sos[base];

        }

        cout << ans << "\n";
    }

    return 0;
}

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