Submission #334788

#	Time	Username	Problem	Language	Result	Execution time	Memory
334788		YJU	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1337 ms	42896 KiB

snake_escaping

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=(1LL<<21);
const ll K=350;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll n,q,L,f[N],b[N],bcnt[N],u[N],p0,p1,p2,res;
string s;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>q>>s;
	L=(1<<n);
	REP(i,L){
		f[i]=b[i]=u[i]=s[i]-'0';
		bcnt[i]=bcnt[i>>1]+(i&1);
	}
	for(int i=1;i<L;i<<=1){
		REP(j,L){
			if(i&j)f[j]+=f[i^j],b[i^j]+=b[j];
		}
	}
	while(q--){
		cin>>s;
		p0=p1=p2=res=0;
		REP(i,n){
			if(s[n-i-1]=='0')p0|=(1<<i);
			else if(s[n-i-1]=='1')p1|=(1<<i);
			else p2|=(1<<i);
		}
		if(bcnt[p0]<=6){
			for(int bit=p0;;bit=(bit-1)&p0){
				if(bcnt[bit]&1)res-=b[bit|p1];
				else res+=b[bit|p1];
				if(!bit)break;
			}
		}else if(bcnt[p1]<=6){
			for(int bit=p1;;bit=(bit-1)&p1){
				if(bcnt[bit^p1]&1)res-=f[bit|p2];
				else res+=f[bit|p2];
				if(!bit)break;
			}
		}else{
			for(int bit=p2;;bit=(bit-1)&p2){
				res+=u[p1|bit];
				if(!bit)break;
			}
		}
		cout<<res<<"\n";
	}
	return 0;
}

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