Submission #954392

#	Time	Username	Problem	Language	Result	Execution time	Memory
954392		KLPP	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1703 ms	60148 KiB

snake_escaping

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
lld val[2000000];
lld super[2000000];
lld sub[2000000];
string s;
vector<int> cnt0;
vector<int> cnt1;
vector<int> cnt2;
void solve() {
	int n,q;
	cin>>n>>q;
	cin>>s;
	rep(i,0,(1<<n)){
		val[i]=s[i]-'0';
		super[i]=s[i]-'0';
		sub[i]=s[i]-'0';
	}
	rep(i,0,n){
		rep(msk,0,(1<<n)){
			if((msk&(1<<i))){
				sub[msk]+=sub[msk-(1<<i)];
			}else{
				super[msk]+=super[msk+(1<<i)];
			}
		}
	}
	//rep(msk,0,(1<<n))cout<<sub[msk]<<endl;
	while(q--){
		cnt0.clear();
		cnt1.clear();
		cnt2.clear();
		cin>>s;
		int curmsk=0;
		rep(i,0,n){
			if(s[n-1-i]=='0')cnt0.push_back(i);
			if(s[n-1-i]=='1')cnt1.push_back(i),curmsk+=(1<<i);
			if(s[n-1-i]=='?')cnt2.push_back(i);
		}
		if((int)cnt2.size()<=7){
			lld ans=0;
			rep(msk,0,(1<<cnt2.size())){
				int genms=curmsk;
				rep(j,0,(int)cnt2.size()){
					if((msk&(1<<j))){
						genms+=(1<<cnt2[j]);
					}
				}
				ans+=val[genms];
				//cout<<"G"<<genms<<endl;
			}
			cout<<ans<<"\n";
		}else{
			if((int)cnt1.size()<=6){
				//few 1's
				trav(a,cnt2)curmsk+=(1<<a);
				lld ans=0;
				rep(msk,0,(1<<cnt1.size())){
					int genms=curmsk;
					int mlt=1;
					rep(j,0,(int)cnt1.size()){
						if((msk&(1<<j))){
							mlt*=-1;
							genms-=(1<<cnt1[j]);
						}
					}
					ans+=mlt*sub[genms];
					//cout<<"G "<<genms<<" "<<sub[genms]<<endl;
				}
				cout<<ans<<"\n";
			}else{
				lld ans=0;
				rep(msk,0,(1<<cnt0.size())){
					int genms=curmsk;
					int mlt=1;
					rep(j,0,(int)cnt0.size()){
						if((msk&(1<<j))){
							mlt*=-1;
							genms+=(1<<cnt0[j]);
						}
					}
					ans+=mlt*super[genms];
					//cout<<"G "<<genms<<" "<<super[genms]<<endl;
				}
				cout<<ans<<"\n";
			}
		}
	}
}


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	//cin>>tt;
	while(tt--){
		solve();
	}
}

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