제출 #234937

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
234937		amoo_safar	Snake Escaping (JOI18_snake_escaping)	C++14	75 / 100	2089 ms	39448 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;
	cin >> 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;
		for(int i = 0; i < L; i++){
			if(s[i] == '1') mk1 |= (1 << (L - 1 - i));
			if(s[i] == '0') mk0 |= (1 << (L - 1 - i));	
		}
		if(__builtin_popcount(mk0) < __builtin_popcount(mk1)){
			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: 0 / 25