Submission #1278961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278961		PieArmy	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	480 ms	25172 KiB

snake_escaping

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)

int n,m,q;
int arr[1<<20];
int bir[1<<20],sif[1<<20];
int say[1<<20];

int main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>m>>q;
	n=(1<<m);
	for(int i=0;i<n;i++){
		char c;cin>>c;
		arr[i]=c-'0';
		bir[i]+=arr[i];
		sif[i]+=arr[i];
		say[i]=__builtin_popcount(i);
	}
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			if((j>>i)&1){
				sif[j-(1<<i)]+=sif[j];
			}
			else bir[j+(1<<i)]+=bir[j];
		}
	}
	while(q--){
		string s;cin>>s;
		reverse(s.begin(),s.end());
		int cnta=0,cntb=0,cntc=0;
		for(int i=0;i<m;i++){
			if(s[i]=='0')cnta++;
			else if(s[i]=='1')cntb++;
			else cntc++;
		}
		if(cntc<=6){
			int mask=0,x=0;
			for(int i=0;i<m;i++){
				if(s[i]=='?')mask+=(1<<i);
				else if(s[i]=='1')x+=(1<<i);
			}
			int ans=arr[x];
			for(int i=mask;i>0;i=((i-1)&mask)){
				ans+=arr[x^i];
			}
			cout<<ans<<endl;
		}
		else if(cntb<=6){
			int mask=0,x=0;
			for(int i=0;i<m;i++){
				if(s[i]=='1'){
					mask+=(1<<i);
					x+=(1<<i);
				}
				else if(s[i]=='?')x+=(1<<i);
			}
			int ans=bir[x];
			for(int i=mask;i>0;i=((i-1)&mask)){
				int k=1;
				if((say[i])&1)k=-1;
				ans+=bir[x^i]*k;
			}
			cout<<ans<<endl;
		}
		else{
			int mask=0,x=0;
			for(int i=0;i<m;i++){
				if(s[i]=='0')mask+=(1<<i);
				else if(s[i]=='1')x+=(1<<i);
			}
			int ans=sif[x];
			for(int i=mask;i>0;i=((i-1)&mask)){
				int k=1;
				if((say[i])&1)k=-1;
				ans+=sif[x^i]*k;
			}
			cout<<ans<<endl;
		}
	}
}

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