Submission #1036310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036310		Hanksburger	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1263 ms	42324 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
int a[1048580], b[1048580], c[1048580];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i=0; i<(1<<n); i++)
    {
        char x;
        cin >> x;
        a[i]=b[i]=c[i^((1<<n)-1)]=x-'0';
    }
    for (int i=0; i<n; i++)
        for (int j=0; j<(1<<n); j++)
            if (j&(1<<i))
                b[j]+=b[j^(1<<i)], c[j]+=c[j^(1<<i)];
    for (int i=0; i<m; i++)
    {
        string s;
        cin >> s;
        reverse(s.begin(), s.end());
        vector<int> v0, v1, v2;
        for (int j=0; j<n; j++)
        {
            if (s[j]=='0')
                v0.push_back(j);
            else if (s[j]=='1')
                v1.push_back(j);
            else
                v2.push_back(j);
        }
        if (v0.size()<=v1.size() && v0.size()<=v2.size())
        {
            int x=0, sz=v0.size(), ans=0;
            for (int j=0; j<n; j++)
                if (s[j]=='0' || s[j]=='?')
                    x^=(1<<j);
            for (int j=0; j<(1<<sz); j++)
            {
                int y=0, cnt=0;
                for (int k=0; k<sz; k++)
                {
                    
                    if (j&(1<<k))
                    {
                        y^=(1<<v0[k]);
                        cnt++;
                    }
                }
                if (cnt&1)
                    ans-=c[x^y];
                else
                    ans+=c[x^y];
            }
            cout << ans << '\n';
        }
        else if (v1.size()<=v0.size() && v1.size()<=v2.size())
        {
            int x=0, sz=v1.size(), ans=0;
            for (int j=0; j<n; j++)
                if (s[j]=='1' || s[j]=='?')
                    x^=(1<<j);
            for (int j=0; j<(1<<sz); j++)
            {
                int y=0, cnt=0;
                for (int k=0; k<sz; k++)
                {
                    if (j&(1<<k))
                    {
                        y^=(1<<v1[k]);
                        cnt++;
                    }
                }
                if (cnt&1)
                    ans-=b[x^y];
                else
                    ans+=b[x^y];
            }
            cout << ans << '\n';
        }
        else
        {
            int x=0, sz=v2.size(), ans=0;
            for (int j=0; j<n; j++)
                if (s[j]=='1')
                    x^=(1<<j);
            for (int j=0; j<(1<<sz); j++)
            {
                int y=0;
                for (int k=0; k<sz; k++)
                    if (j&(1<<k))
                        y^=(1<<v2[k]);
                ans+=a[x^y];
            }
            cout << ans << '\n';
        }
    }
}

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