Submission #64590

#	Time	Username	Problem	Language	Result	Execution time	Memory
64590		keko37	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1944 ms	51616 KiB

snake_escaping

#include<iostream>
#include<cstdio>

using namespace std;

const int MAXN = (1<<20) + 5;

int n, q, a, b, c, sol, mask, N, rev, count, i, j, tc;
char ss[MAXN];
char l[30], cc;
int val[MAXN], sum0[MAXN], sum1[MAXN], pc[MAXN];

int main () {
	scanf("%d%d", &n, &q);
	scanf("%s", ss);
	for (i=0; i<(1<<n); i++) {
		val[i] = ss[i] - '0';
		pc[i] = pc[i - (i&-i)]+1;
		sum0[i] = val[i];
	}
	for (int i=0; i<(1<<n); i++) {
		sum1[i] = val[i ^ ((1<<n) - 1)];
	}
	for (i=0; i<n; i++) {
		for (j=0; j<(1<<n); j++) {
			if (j & (1<<i)) sum0[j] += sum0[j ^ (1<<i)];
			if (j & (1<<i)) sum1[j] += sum1[j ^ (1<<i)];
		}
	}
	for (tc=0; tc<q; tc++) {
		a = b = c = 0;
		do {
			cc = getchar();
		} while (!(cc=='0' || cc=='1' || cc=='?'));
		for (i=0; i<n; i++) {
			if (i>0) cc = getchar();
			l[i] = cc;
			if (l[i] == '?') {
				a ^= (1<<(n-1-i));
			} else if (l[i] == '0') {
				b ^= (1<<(n-1-i));
			} else {
				c ^= (1<<(n-1-i));
			}
		}
		sol = 0;
		if (pc[a] <= pc[b] && pc[a] <= pc[c]) {
			for (mask = a; ; mask = (mask - 1) & a) {
				sol += val[mask | c];
				if (!mask) break;
			}
		} else if (pc[b] <= pc[a] && pc[b] <= pc[c]) {
			for (mask = b; ; mask = (mask-1) & b) {
				rev = mask | a;
				if (pc[rev] & 1) {
					sol -= sum1[rev];
				} else {
					sol += sum1[rev];
				}
				if (!mask) break;
			}
			if (sol < 0) sol = -sol;
		} else {
			for (mask = c; ; mask = (mask - 1) & c) {
				rev = mask | a;
				if (pc[rev] & 1) {
					sol -= sum0[rev];
				} else {
					sol += sum0[rev];
				}
				if (!mask) break;
			}
			if (sol < 0) sol = -sol;
		}
		printf("%d\n", sol);
	}
	return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~
snake_escaping.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", ss);
  ~~~~~^~~~~~~~~~

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