Submission #260335

#	Time	Username	Problem	Language	Result	Execution time	Memory
260335		Goolakh	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1279 ms	39320 KiB

snake_escaping

// FUCKED UP FUCKED UP FUCKED UP FUCKED UP FUCKED UP
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math")

#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair

typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=2e3+10, maxm=1e6+10, lg=21, mod=1e9+7, inf=1e18;

#define bone(x) (__builtin_popcount(x))

ll L,Q;
string s;
ll s0[1<<lg],s1[1<<lg];

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin>>L>>Q>>s;
	for(int i=0;i<SZ(s);i++) s1[i]=s0[((1<<L)-1)^i]=s[i]-'0';
	for(int i=0;i<L;i++)for(int m=0;m<SZ(s);m++)if(m>>i&1) s0[m^(1<<i)]+=s0[m], s1[m^(1<<i)]+=s1[m];
	while(Q--){
		string t; cin>>t; reverse(all(t));
		ll t0=0,t1=0,tq=0;
		for(int i=0;i<L;i++){
			if(t[i]=='0') t0^=(1<<i);
			if(t[i]=='1') t1^=(1<<i);
			if(t[i]=='?') tq+=(1<<i);
		}
		ll mn=min({bone(t0),bone(t1),bone(tq)}),ans=0;
		if(mn==bone(tq)){
			for(ll sub=tq;;sub=(sub-1)&tq){
				ans+=s[sub^t1]-'0';
				if(!sub) break;
			};
		}
		else if(mn==bone(t1)){
			for(ll sub=t1;;sub=(sub-1)&t1){
				ans+=(bone(sub)%2 ? +1:-1)*s0[sub^t0];
				if(!sub) break;
			}
		}
		else if(mn==bone(t0)){
			for(ll sub=t0;;sub=(sub-1)&t0){
				ans+=(bone(sub)%2 ? +1:-1)*s1[sub^t1];
				if(!sub) break;
			}
		}
		cout<<abs(ans)<<'\n';
	}
	
	return 0;
}



 

Compilation message (stderr)

snake_escaping.cpp:20:58: warning: overflow in implicit constant conversion [-Woverflow]
 const ll maxn=2e3+10, maxm=1e6+10, lg=21, mod=1e9+7, inf=1e18;
                                                          ^~~~

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