Submission #234942

#	Time	Username	Problem	Language	Result	Execution time	Memory
234942		amoo_safar	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	863 ms	20688 KiB

snake_escaping

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 20;

int s1[(1 << Log) + 2];
int s0[(1 << Log) + 2];
int L, Q;
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> L >> Q;
	str s, t;
	cin >> s;
	t = s;
	for(int i = 0; i < (1 << L); i++) s1[i] = s[i] - '0';
	for(int i = 0; i < (1 << L); i++) s0[((1<<L) - 1) ^ i] = s[i] - '0';
	for(int l = 0; l < L; l++)
		for(int i = 0; i < (1 << L); i++)
			if(i >> l & 1) s1[i ^ (1 << l)] += s1[i];
	for(int l = 0; l < L; l++)
		for(int i = 0; i < (1 << L); i++)
			if(i >> l & 1) s0[i ^ (1 << l)] += s0[i];

	while(Q --){

		cin >> s;
		int mk0 = 0, mk1 = 0, mkq = 0;
		int c0 = 0, c1 = 0, cq = 0;
		for(int i = 0; i < L; i++){
			if(s[i] == '1') mk1 |= (1 << (L - 1 - i)), c1 ++;
			if(s[i] == '0') mk0 |= (1 << (L - 1 - i)), c0 ++;
			if(s[i] == '?') mkq |= (1 << (L - 1 - i)), cq ++;
		}
		if(cq <= min(c0, c1)){
			int res = t[mk1]-'0';
			int sub = mkq;
			while(sub){
				res += t[sub + mk1] - '0';
				sub = mkq & (sub - 1);
			}
			cout << res << '\n';
			continue;
		}
		if(c0 <= c1){
			int res = s1[mk1];
			int sub = mk0;
			while(sub){
				res += (__builtin_popcount(sub) & 1 ? -1 : 1) * s1[sub + mk1];
				sub = mk0 & (sub - 1);
			}
			cout << res << '\n';
		} else {
			int res = s0[mk0];
			int sub = mk1;
			while(sub){
				res += (__builtin_popcount(sub) & 1 ? -1 : 1) * s0[sub + mk0];
				sub = mk1 & (sub - 1);
			}
			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