Submission #1300391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300391		StefanSebez	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1744 ms	21736 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=(1<<20)+50;
int L,q;
int f[N],F0[N],F1[N];
int main(){
    scanf("%i%i",&L,&q);
    string s;cin>>s;
    int n=1<<L;
    //SOS dp
    for(int i=0;i<n;i++) F0[i]=F1[i]=f[i]=s[i]-'0';
    for(int i=0,e=1;i<L;i++,e<<=1){
        for(int mask=0;mask<n;mask++){
            if(mask&e) F0[mask]+=F0[mask^e];
        }
        for(int mask=n-1;mask>=0;mask--){
            if(!(mask&e)) F1[mask]+=F1[mask^e];
        }
    }
    while(q--){
        string t;cin>>t;
        int cnt[3]={0};
        for(auto c:t){
            if(c=='0')cnt[0]++;
            if(c=='1')cnt[1]++;
            if(c=='?')cnt[2]++;
        }
        ll res=0;
        if(cnt[1]<=L/3){
            int mask0=0,mask1=0;
            for(int i=L-1,e=1;i>=0;i--,e<<=1){
                if(t[i]=='?')mask0^=e;
                if(t[i]=='1')mask1^=e;
            }
            for(int mask=mask1;mask>=0;mask=(mask-1)&mask1){
                if(__builtin_popcount(mask)%2==__builtin_popcount(mask1)%2)res+=F0[mask0^mask];
                else res-=F0[mask0^mask];
                if(mask==0)break;
            }
        }
        else if(cnt[0]<=L/3){
            int mask0=0,mask1=0;
            for(int i=L-1,e=1;i>=0;i--,e<<=1){
                if(t[i]!='?')mask0^=e;
                if(t[i]=='1'||t[i]=='?')mask1^=e;
            }
            for(int mask=mask1;mask<n;mask=(mask+1)|mask1){
                if(__builtin_popcount(mask)%2==__builtin_popcount(mask1)%2)res+=F1[mask0&mask];
                else res-=F1[mask0&mask];
            }
        }
        else{
            int mask0=0,mask1=0;
            for(int i=L-1,e=1;i>=0;i--,e<<=1){
                if(t[i]=='1')mask0^=e;
                if(t[i]=='?')mask1^=e;
            }
            for(int mask=mask1;mask>=0;mask=(mask-1)&mask1){
                res+=f[mask0^mask];
                if(mask==0)break;
            }
        }
        printf("%lld\n",res);
    }
    return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     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