Submission #404597

#	Time	Username	Problem	Language	Result	Execution time	Memory
404597		Antekb	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1459 ms	43472 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
const int L=20;
int tab[1<<L], pod[1<<L], nad[1<<L];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
	int l, q;
	cin>>l>>q;
	string s;
	cin>>s;
	int n=s.size();
	for(int i=0; i<n; i++)tab[i]=pod[i]=nad[i]=s[i]-'0';
	for(int j=0; j<l; j++){
		for(int i=0; i<n; i++)
		{
			if(i&(1<<j))pod[i]+=pod[i^(1<<j)];
			else nad[i]+=nad[i^(1<<j)];
		}
	}
	/*for(int i=0; i<n; i++){
		cout<<i<<" "<<pod[i]<<" "<<nad[i]<<"\n";
	}*/
	for(int i=0; i<q; i++){
		int c1=0, c2=0, c3=0;
		string t;
		cin>>t;
		reverse(t.begin(), t.end());
		for(int j=0; j<l; j++){
			if(t[j]=='0')c1++;
			else if(t[j]=='1')c2++;
			else c3++;
		}
		if(c1==min({c1, c2, c3})){
			int x=0, y=0, ans=0;
			for(int j=0; j<l; j++)if(t[j]=='0')x+=(1<<j);
			for(int j=0; j<l; j++)if(t[j]=='1')y+=(1<<j);
			for(int j=x; ; j=(j-1)&x){
				//cout<<y+j<<" "<<bitset<3>(y+j)<<" ";
				if(__builtin_popcount(j)&1){
					ans-=nad[y+j];
				}
				else ans+=nad[y+j];
				if(j==0)break;
			}
			cout<<ans<<"\n";
		}
		else if(c2==min({c1, c2, c3})){
			int x=0, y=0, ans=0;
			for(int j=0; j<l; j++)if(t[j]=='1')x+=(1<<j);
			for(int j=0; j<l; j++)if(t[j]!='0')y+=(1<<j);
			for(int j=x; ; j=(j-1)&x){
				//cout<<y+j<<" "<<bitset<3>(y+j)<<" ";
				if(__builtin_popcount(j)&1){
					ans-=pod[y-j];
				}
				else ans+=pod[y-j];
				if(j==0)break;
			}
			cout<<ans<<"\n";
		}
		else{
			int ans=0, x=0, y=0;
			for(int j=0; j<l;j ++){
				if(t[j]=='?')x+=(1<<j);
				if(t[j]=='1')y+=(1<<j);
			}
			for(int j=x;  ; j=(j-1)&x){
				ans+=tab[y+j];
				if(j==0)break;
			}
			cout<<ans<<"\n";
		}
	}
}

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