Submission #225244

#	Time	Username	Problem	Language	Result	Execution time	Memory
225244		MKopchev	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1164 ms	54520 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
const int nmax=(1<<20)+42;

int l,n,q;

int inp[nmax];

char cur[25];

int cnt_bits[nmax];

long long dp_ones[nmax],dp_zeros[nmax];

int main()
{
    scanf("%i%i",&l,&q);

    n=1<<l;

    for(int i=1;i<n;i++)
    {
        cnt_bits[i]=cnt_bits[i/2]+i%2;
    }

    for(int i=0;i<n;i++)
    {
        char c=getchar();
        while('0'>c||c>'9')c=getchar();

        inp[i]=c-'0';
    }

    for(int i=0;i<n;i++)dp_ones[i]=inp[n-1-i];

    for(int i=0;i<l;i++)
        for(int mask=0;mask<n;mask++)
            if((mask&(1<<i)))dp_ones[mask]+=dp_ones[mask-(1<<i)];

    for(int i=0;i<n;i++)dp_zeros[i]=inp[i];

    for(int i=0;i<l;i++)
        for(int mask=n-1;mask>=0;mask--)
            if((mask&(1<<i)))dp_zeros[mask]+=dp_zeros[mask-(1<<i)];

    for(int t=1;t<=q;t++)
    {
        long long output=0;

        int question=0;

        int one=0;

        int zero=0;

        for(int j=1;j<=l;j++)
        {
            char c=getchar();
            while(c!='?'&&c!='0'&&c!='1')c=getchar();

            if(c=='?')question+=(1<<(l-j));
            if(c=='0')zero+=(1<<(l-j));
            if(c=='1')one+=(1<<(l-j));
        }

        if(cnt_bits[question]<=cnt_bits[zero]&&cnt_bits[question]<=cnt_bits[one])
        {
            int mask=question;

            while(true)
            {
                output+=inp[one+mask];

                if(mask==0)break;

                mask=(mask-1)&question;
            }
        }
        else if(cnt_bits[zero]<=cnt_bits[one])
        {
            int mask=zero;

            while(true)
            {
                if(cnt_bits[mask]%2)output+=dp_ones[question+mask];
                else output-=dp_ones[question+mask];

                if(mask==0)break;
                mask=(mask-1)&zero;
            }
        }
        else
        {
            int mask=one;

            while(true)
            {
                if(cnt_bits[mask]%2)output+=dp_zeros[question+mask];
                else output-=dp_zeros[question+mask];

                if(mask==0)break;
                mask=(mask-1)&one;
            }
        }

        output=abs(output);
        printf("%lld\n",output);
    }
    return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&l,&q);
     ~~~~~^~~~~~~~~~~~~~

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