제출 #535650

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535650		Arnch	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	593 ms	10756 KiB

snake_escaping

// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define endl '\n'

constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;

int a[N], fd[N], fu[N], fu2[N];

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	int l, q; cin >>l >>q;
	string s; cin >>s;
	for(int i = 0; i < Sz(s); i++) {
		a[i] = s[i] - '0';
	}

	int to = (1 << l) - 1;
	for(int i = 0; i < (1 << l); i++) {
		fd[i] = a[i], fu2[i ^ to] = a[i];
	}
	for(int i = 0; i < l; i++) {
		for(int mask = 0; mask < (1 << l); mask++) {
			if((mask >> i) & 1) {
				fd[mask] += fd[mask ^ (1 << i)];
				fu2[mask] += fu2[mask ^ (1 << i)];
			}
		}
	}

	for(int mask = 0; mask < (1 << l); mask++) {
		fu[mask] = fu2[mask ^ to];
	}


	while(q--) {
		cin >>s;
		int cnt0 = 0, cnt1 = 0, cnt = 0;
		for(int i = 0; i < Sz(s); i++) {
			cnt0 += (s[i] == '0');
			cnt1 += (s[i] == '1');
			cnt += (s[i] == '?');
		}
		int mask = 0, mask2 = 0;

		if(cnt <= 6) {
			for(int i = 0; i < Sz(s); i++) {
				if(s[i] == '?') mask2 += (1 << (Sz(s) - i - 1));
				if(s[i] == '1') mask += (1 << (Sz(s) - i - 1));
			}
			int ans = a[mask];
			for(int i = mask2; i > 0; i = (i - 1) & mask2) {
				ans += a[i + mask];
			}
			cout<<ans <<endl;
			continue;
		}

		if(cnt1 <= 6) {
			for(int i = 0; i < Sz(s); i++) {
				if(s[i] == '1') mask2 += (1 << (Sz(s) - i - 1));
				if(s[i] == '?') mask += (1 << (Sz(s) - i - 1));
			}
			int cnte = __builtin_popcount(mask2) & 1, ans = 0;
			for(int i = mask2; i > 0; i = (i - 1) & mask2) {
				if((__builtin_popcount(i) & 1) == cnte) ans += fd[i + mask];
				else ans -= fd[i + mask];
			}
			if(cnte == 0) ans += fd[mask];
			else ans -= fd[mask];
			cout<<ans <<endl;
			continue;
		}

		for(int i = 0; i < Sz(s); i++) {
			if(s[i] == '0') mask2 += (1 << (Sz(s) - i - 1));
			if(s[i] == '1') mask += (1 << (Sz(s) - i - 1));
		}
		int cnte = 0, ans = 0;
		for(int i = mask2; i > 0; i = (i - 1) & mask2) {
			if((__builtin_popcount(i) & 1) == cnte) ans += fu[i + mask];
			else ans -= fu[i + mask];
		}
		ans += fu[mask];
		cout<<ans <<endl;
	}

	

	
    return 0;
}

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