Submission #1180507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180507		Szymon_Pilipczuk	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1161 ms	29756 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
int pot[21];
int tox[1048576];
long long dp1[1048576];
long long dp0[1048576];
int c[3];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    pot[0] = 1;
    for(int i = 1;i<=20;i++) pot[i] = 2*pot[i-1];
    int l,q;
    cin>>l>>q;
    for(int i = 0;i<pot[l];i++)
    {
        char c;
        cin>>c;
        tox[i] = int(c)-48;
        dp1[i] = tox[i];
        dp0[i] = tox[i];
        //cout<<dp1[i]<<"   "<<i<<"\n";
    }
    for(int i = 0;i<l;i++)
    {
        for(int j = 0;j<pot[l];j++)
        {
            if(j & pot[i])
            {
                dp1[j] += dp1[j-pot[i]];
            }
            //cout<<dp1[j]<<" "<<i+1<<" "<<j<<"\n";
        }
    }
    for(int i = 0;i<l;i++)
    {
        for(int j = 0;j<pot[l];j++)
        {
            if(!(j&pot[i]))
            {
                dp0[j] += dp0[j+pot[i]];
            }
        }
    }

    for(int w = 0;w<q;w++)
    {
        int ans = 0;
        int p[l];
        vector<int>cpl;
        vector<int>c0l;
        vector<int>c1l;
        int lq = 0;
        int l1 = 0;
        int l0 = 0;
        for(int j = l-1;j>=0;j--)
        {
            char c;
            cin>>c;
            if(c == '?')
            {
                p[j] = 2;
                l1+=pot[j];
                cpl.push_back(j);
            }
            else
            {
                p[j] = int(c)-48;
                if(p[j] == 0)
                {
                    c0l.push_back(j);
                }
                else
                {
                    lq+=pot[j];
                    l1+=pot[j];
                    l0+=pot[j];
                    c1l.push_back(j);
                }
            }
        }

        if(min(min(c0l.size(),c1l.size()),cpl.size()) == cpl.size())
        {
            for(int i = 0;i<pot[cpl.size()];i++)
            {
                int l2 = lq;
                for(int j = 0;j<cpl.size();j++)
                {
                    if(i & pot[j])
                    {
                        l2+= pot[cpl[j]];
                    }
                }
                ans += tox[l2];
            }
        }
        else if(min(c0l.size(),c1l.size()) == c1l.size())
        {
            for(int i = 0;i<pot[c1l.size()];i++)
            {
                int l2 = l1;
                int c = c1l.size()%2;
                for(int j = 0;j<c1l.size();j++)
                {
                    if(i & pot[j])
                    {
                        l2-=pot[c1l[j]];
                        c = c^1;
                    }
                }
                if(c == 0) ans+=dp1[l2];
                else ans-=dp1[l2];
            }
        }
        else
        {
            for(int i = 0;i<pot[c0l.size()];i++)
            {
                int l2 = l0;
                int c = c0l.size()%2;
                for(int j = 0;j<c0l.size();j++)
                {
                    if(i&pot[j])
                    {
                        l2+=pot[c0l[j]];
                        c = c^1;
                    }
                }
                if(c == 0) ans+=dp0[l2];
                else ans-=dp0[l2];

            }
        }
        cout<<abs(ans)<<"\n";

    }

}

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