Submission #954422

#	Time	Username	Problem	Language	Result	Execution time	Memory
954422		mat_jur	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	520 ms	42068 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

bool is_digit(char c) {
	return c >= '0';
}

int fastin(){
	int x = 0;
	char c;
	while (is_digit(c = getchar_unlocked())) {
		x = x * 10 + c - '0';
	}
	return x;
}

void write_int(unsigned long x) {
	char t[19];
	int i = 0;
	do {
		int d = x%10;
		t[i++] = '0'+d;
		x /= 10;
	} while (x > 0) ;

	while (--i >= 0) {
		putchar_unlocked(t[i]);
	}
	putchar_unlocked('\n');
}

int main() {
	int l = fastin(), q = fastin();
	debug(l);
	debug(q);
	int n = (1<<l);

	vector<int> a(n);
	for(int i = 0; i < n; ++i) {
		char c = getchar_unlocked();
		debug(c);
		a[i] = c-'0';
	}

	char nl = getchar_unlocked();
	debug(a);

	vector<int> sub(n), sup(n);
	for(int i = 0; i < n; ++i) sub[i] = sup[i] = a[i];

	for(int i = 0; i < l; ++i) {
		for(int j = 0; j < n; ++j) {
			if(j&(1<<i)) sub[j] += sub[j^(1<<i)];
			else sup[j] += sup[j^(1<<i)];
		}
	}

	while (q--) {
		int mask[3];
		mask[0] = mask[1] = mask[2] = 0;
		for(int i = l-1; i >= 0; --i) {
			char c = getchar_unlocked();
			if(c == '?') mask[2] |= (1<<i);
			else mask[c-'0'] |= (1<<i);
		}
		nl = getchar_unlocked();
		
		int res = 0;
		int sz0 = __builtin_popcount(mask[0]), sz1 = __builtin_popcount(mask[1]), sz2 = __builtin_popcount(mask[2]);
		if(sz1 <= sz2 && sz1 <= sz0) {
			for(int s = mask[1]; ; s = (s-1)&mask[1]) {
				res += sub[s|mask[2]] * (__builtin_popcount(s) % 2 == sz1 % 2 ? 1 : -1);
				if(!s) break;
			}
		}
		else if(sz0 <= sz1 && sz0 <= sz2) {
			for(int s = mask[0]; ; s = (s-1)&mask[0]) {
				res += sup[s|mask[1]] * ((sz0-__builtin_popcount(s)) % 2 == sz0 % 2 ? 1 : -1);
				if(!s) break;
			}
		} else {
			for(int s = mask[2]; ; s = (s-1)&mask[2]) {
				res += a[s|mask[1]];
				if(!s) break;
			}
		}

		write_int(res);
	}

	return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:60:7: warning: variable 'nl' set but not used [-Wunused-but-set-variable]
   60 |  char nl = getchar_unlocked();
      |       ^~

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