Submission #1316227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316227		JuanJL	Snake Escaping (JOI18_snake_escaping)	C++20	0 / 100	1 ms	332 KiB

snake_escaping

#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i<b; i++)
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;

const int MAXL = 21;
const int MAXP = (1<<20);

ll dp1[MAXP];
ll dp2[MAXP];
ll cost[MAXP];

ll L,Q;
string s; 
vector<ll> one;
	vector<ll> zero;
	vector<ll> qsy;
	ll res = 0;
	ll bina;
	ll newbina;
	ll cnt;

void f1(){ // mascara padre
	for(int y = L; y>=0; y--){
		for(int x=(1<<L)-1; x>=0; x--){
			if(y==L) dp1[x]+=cost[x];
			else dp1[x]=dp1[x]+dp1[x|(1<<y)];
		}
	}
}

void f2(){ // mascara hijo
	for(int y = L; y>=0; y--){
		forn(x,0,1<<L){
			if(y==L) dp2[x]+=cost[x];
			else dp2[x]=dp2[x]+(x&(1<<y)? dp2[x^(1<<y)] :0);
		}
	}
}
int main(){ FIN;
	cin>>L>>Q;
	cin>>s;

	forn(i,0,1<<L){
		dp1[i]=dp2[i]=0;
		cost[i]=s[i]-'0';
	}

	f1();
	f2();

	vector<string> q(Q); forn(i,0,Q) cin>>q[i];
	
	forn(i,0,Q){
		one.clear();
		zero.clear();
		qsy.clear();
		bina = 0;
		forn(j,0,SZ(q[i])){
			if(q[i][j]=='0') zero.pb(j);
			if(q[i][j]=='1') one.pb(j),bina|=(1<<((L-1)-j));
			if(q[i][j]=='?') qsy.pb(j);
		}

		res = 0;
		//cout<<"--------------------\n";

		if(SZ(qsy)<=6){
			forn(h,0,1<<SZ(qsy)){
				newbina = bina;
				forn(k,0,SZ(qsy)) if(h&(1<<k)){
					newbina|=(1<<((L-1)-qsy[k]));
				}
				if(cost[newbina]!=-1) res+=cost[newbina];
			}
		}else if(SZ(one)<=6){
			forn(h,0,SZ(qsy)) bina|=(1<<((L-1)-qsy[h]));
			res=dp2[bina];//f2(bina,0); 
			//cout<<res<<" "; for(int h = L-1; h>=0; h--) cout<<(bina&(1<<h)?1:0); cout<<'\n';
			forn(h,1,1<<SZ(one)){
				cnt = 0;
				newbina = bina;
				forn(k,0,SZ(one)) if(h&(1<<k)){
					newbina^=(1<<((L-1)-one[k]));
					cnt++;
				}
				if(cnt%2==0) res+=dp2[bina];//f2(newbina,0);
				else res-=dp2[bina];//f2(newbina,0);
			}
		}else{
			res=dp1[bina]; //cout<<res<<" "<<bina<<'\n';
			forn(h,1,1<<SZ(zero)){
				cnt = 0;
				newbina = bina;
				forn(k,0,SZ(zero)) if(h&(1<<k)){
					newbina^=(1<<((L-1)-zero[k]));
					cnt++;
				}
				if(cnt%2==0) res+=dp1[newbina];//f1(newbina,0);
				else res-=dp1[newbina];//f1(newbina,0);
			}
		}
		cout<<res<<'\n';
	}
	
	return 0;
}

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