Submission #64564

#	Time	Username	Problem	Language	Result	Execution time	Memory
64564		keko37	Snake Escaping (JOI18_snake_escaping)	C++14	12 / 100	403 ms	66560 KiB

snake_escaping

#include<iostream>

using namespace std;

const int MAXN = 21;

int n, q;
char l[MAXN];
int val[1<<MAXN], sum0[1<<MAXN], sum1[1<<MAXN], pc[1<<MAXN];

void precompute () {
	for (int i=0; i<(1<<n); i++) {
		pc[i] = __builtin_popcount(i);
		sum0[i] = val[i];
		sum1[i] = val[i ^ ((1<<n) - 1)];
	}
	for (int i=0; i<n; i++) {
		for (int 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)];
		}
	}
}

inline bool ok (char c) {
	return (c>='0' && c<='9') || c=='?';
}

inline char readc () {
	char c;
	do {
		c = getchar();
	} while (!ok(c));
	return c;
}

int main () {
	cin >> n >> q;
	for (int i=0; i<(1<<n); i++) {
		val[i] = readc() - '0';
	}
	precompute();
	for (int tc=0; tc<q; tc++) {
		int a = 0, b = 0, c = 0;
		for (int i=0; i<n; i++) {
			l[i] = readc();
			if (l[i] == '?') {
				a ^= (1<<(n-1-i));
			} else if (l[i] == '0') {
				b ^= (1<<(n-1-i));
			} else {
				c ^= (1<<(n-1-i));
			}
		}
		int sol = 0, mask = 0, cnt = 0;
		if (pc[a] <= n/3) {
			do {
				cnt++;
				sol += val[mask | c];
			} while (mask = (mask-a) & a);
		} else if (pc[b] <= n/3) {
			do {
				cnt++;
				if (pc[mask | a] & 1) {
					sol -= sum1[mask | a];
				} else {
					sol += sum1[mask | a];
				}
			} while (mask = (mask-b) & b);
			if (sol < 0) sol = -sol;
		} else {
			do {
				cnt++;
				if (pc[mask | a] & 1) {
					sol -= sum0[mask | a];
				} else {
					sol += sum0[mask | a];
				}
			} while (mask = (mask-c) & c);
			if (sol < 0) sol = -sol;
		}
		printf("%d\n", sol);
	}
	return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:60:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    } while (mask = (mask-a) & a);
             ~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:69:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    } while (mask = (mask-b) & b);
             ~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:79:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    } while (mask = (mask-c) & c);
             ~~~~~^~~~~~~~~~~~~~

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