Submission #398559

#	Time	Username	Problem	Language	Result	Execution time	Memory
398559		pure_mem	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1397 ms	46396 KiB

snake_escaping

#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 1e5 + 12, mod = 1e9 + 7;
const ll INF = 1e18;

int n, q, w[1 << 20], sub[1 << 20], sup[1 << 20], cnt[1 << 20];
                                   
int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> q;
	int all = (1 << n) - 1;
	for(int i = 0;i < (1 << n);i++){
		char x; cin >> x, w[i] = x - '0', cnt[i] = __builtin_popcount(i);
		sup[i] = sub[all ^ i] = w[i];
	}
	for(int i = 0;i < n;i++){
		for(int j = 0;j < (1 << n);j++){
			if((j >> i) & 1)
				sup[j] += sup[j ^ (1 << i)];
		}
		for(int j = 0;j < (1 << n);j++){
			if((j >> i) & 1)
				sub[j] += sub[j ^ (1 << i)];
		}
	}
	for(int i = 0;i < q;i++){
		int A = 0, B = 0, C = 0;
		int cA = 0, cB = 0, cC = 0;
		for(int j = 1;j <= n;j++){
			char x;
			cin >> x;
			if(x == '0')
				cA += 1, A ^= (1 << (n - j));
			else if(x == '1')
				cB += 1, B ^= (1 << (n - j));
			else
				cC += 1, C ^= (1 << (n - j));
		}
		int ans = 0;
		if(cA <= cC && cA <= cB){
			for(int mask = A;mask >= 0;mask = (mask - 1) & A){
				if((cnt[A] - cnt[mask]) & 1)
					ans -= sub[mask | C];
				else
					ans += sub[mask | C];	
				if(mask == 0)
					break;
			}		
		}
		else if(cB <= cA && cB <= cC){
			for(int mask = B;mask >= 0;mask = (mask - 1) & B){
				if((cnt[B] - cnt[mask]) & 1) 
					ans -= sup[mask | C];
				else
					ans += sup[mask | C];
				if(mask == 0)
					break;
			}	
		}
		else{
			for(int mask = C;mask >= 0;mask = (mask - 1) & C){
				ans += w[B | mask];
				if(mask == 0)
					break;
			}
		}
		cout << ans << "\n";
	}
}

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