Submission #161423

#	Time	Username	Problem	Language	Result	Execution time	Memory
161423		HungAnhGoldIBO2020	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1185 ms	43416 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1e5;
int f0[N],f1[N],val[N];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int q,n,m,i,j,k,l,m1,m2,m3,ans;
	cin>>n>>q;
	string s;
	cin>>s;
	k=(1<<n)-1;
	for(i=0;i<=k;i++){
		val[i]=f1[i]=f0[k^i]=s[i]-'0';
	}
	for(i=0;i<n;i++){
		for(j=0;j<=k;j++){
			if((j&(1<<i))){
				f1[j]+=f1[j^(1<<i)];
				f0[j]+=f0[j^(1<<i)];
			}
		}
	}
//	cout<<f0[4]<<' '<<f0[0]<<endl;
	for(i=1;i<=q;i++){
		m1=m2=m3=ans=0;
		cin>>s;
		for(j=0;j<n;j++){
			if(s[n-j-1]=='0'){
				m1|=(1<<j);
			}
			if(s[n-j-1]=='1'){
				m2|=(1<<j);
			}
			if(s[n-j-1]=='?'){
				m3|=(1<<j);
			}
		}
		if(__builtin_popcount(m1)<=n/3){
			for(j=m1;j;j=(j-1)&m1){
				if((__builtin_popcount(m1)&1)==(__builtin_popcount(j)&1)){
					ans+=f0[m3|j];
				}
				else{
					ans-=f0[m3|j];
				}
			}
//			cout<<m3<<'\n';
			if((__builtin_popcount(m1)&1)==(__builtin_popcount(j)&1)){
				ans+=f0[m3|j];
			}
			else{
				ans-=f0[m3|j];
			}
			cout<<ans<<'\n';
//			cout<<"cac"<<'\n';
			continue;
		}
		if(__builtin_popcount(m2)<=n/3){
			for(j=m2;j;j=(j-1)&m2){
				if((__builtin_popcount(m2)&1)==(__builtin_popcount(j)&1)){
					ans+=f1[m3|j];
				}
				else{
					ans-=f1[m3|j];
				}
			}
			if((__builtin_popcount(m2)&1)==(__builtin_popcount(j)&1)){
				ans+=f1[m3|j];
			}
			else{
				ans-=f1[m3|j];
			}
			cout<<ans<<'\n';
			continue;
		}
		if(__builtin_popcount(m3)<=n/3){
			ans=val[m2];
			for(j=m3;j;j=(j-1)&m3){
				ans+=val[m2|j];
			}
			cout<<ans<<'\n';
			continue;
		}
	}	
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:8:10: warning: unused variable 'm' [-Wunused-variable]
  int q,n,m,i,j,k,l,m1,m2,m3,ans;
          ^
snake_escaping.cpp:8:18: warning: unused variable 'l' [-Wunused-variable]
  int q,n,m,i,j,k,l,m1,m2,m3,ans;
                  ^

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