Submission #860636

#	Time	Username	Problem	Language	Result	Execution time	Memory
860636		phoenix0423	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	554 ms	38008 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int maxn = 1<<20 + 5;
const int sqrtn = 500;
int super[maxn], sub[maxn];
//sos dp + sqrt-sort technique(pigeonhole principle)

int main(void){
	fastio;
	int l, q;
	cin>>l>>q;
	string s;
	cin>>s;
	for(int i = 0; i < (1 << l); i++) sub[i] = super[i] = s[i] - '0';
	for(int i = 0; i < l; i++){
		for(int mask = 0; mask < (1 << l); mask++){
			if(mask & (1 << i)) sub[mask] += sub[mask ^ (1 << i)];
			else super[mask] += super[mask ^ (1 << i)];
		}
	}
	while(q--){
		string t;
		cin>>t;
		int cnt0 = 0, cnt1 = 0, cnt2 = 0;
		int a = 0, b = 0, c = 0; //a = 0, b = 1, c = 2
		for(int i = 0; i < l; i++){
			char x = t[i];
			if(x == '0') cnt0++, a |= (1 << (l - i - 1));
			else if(x == '1') cnt1++, b |= (1 << (l - i - 1));
			else cnt2++, c |= (1 << (l - i - 1));
		}
		int ans = 0;
		if(cnt2 <= cnt0 && cnt2 <= cnt1){
			for(int mask = c; mask > 0; mask = (mask - 1) & c){
				ans += s[mask | b] - '0';
			}
			ans += s[b] - '0';
		}
		else if(cnt0 <= cnt1){
			for(int mask = a; mask > 0; mask = (mask - 1) & a){
				ans += (1 - 2 * (__builtin_popcount(mask) & 1)) * super[mask | b];
			}
			ans += super[b];
		}
		else{
			for(int mask = b; mask > 0; mask = (mask - 1) & b){
				ans += (1 - 2 * (__builtin_popcount(mask) & 1)) * sub[c | (b ^ mask)];
			}
			ans += sub[c | b];
		}
		cout<<ans<<"\n";
	}
}

Compilation message (stderr)

snake_escaping.cpp:11:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   11 | const int maxn = 1<<20 + 5;
      |                     ~~~^~~

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