제출 #544291

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
544291		valerikk	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1022 ms	43184 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int L = 21;
const int M = (1 << L) + 7;
const int K = 6;

int l, q;
int m;
char s[M];
int a[M];
int f[M];
int g[M];

int main() {
	cin >> l >> q >> s;

	m = (1 << l);
	for (int i = 0; i < m; ++i) {
		a[i] = s[i] - '0';
	}

	for (int i = 0; i < m; ++i) {
		f[i] = a[i];
		g[i] = a[i];
	}	
	for (int j = 0; j < l; ++j) {
		for (int i = 0; i < m; ++i) {
			if ((i >> j) & 1) {
				f[i] += f[i ^ (1 << j)];
				g[i ^ (1 << j)] += g[i];
			}
		}
	}

	while (q--) {
		/* int x;
		scanf("%d", &x); */
		static int t[3];
		memset(t, 0, sizeof(t));
		static char tt[L];
		scanf("%s", tt);
		
		for (int i = l - 1; i >= 0; --i) {
			/* t[x % 3] |= (1 << i);
			x /= 3; */
			t[tt[i] == '?' ? 2 : tt[i] - '0'] |= (1 << (l - i - 1)); 
		}

		if (__builtin_popcount(t[1]) <= K) {
			int ans = 0;
			int ppc = __builtin_popcount(t[1]);
			for (int z = t[1]; ; z = (z - 1) & t[1]) {
				ans += (((ppc ^ __builtin_popcount(z)) & 1) ? -1 : 1) * f[t[2] | z];
				if (z == 0) break;
			}
			printf("%d\n", ans);
		} else if (__builtin_popcount(t[0]) <= K) {
			int ans = 0;
			int ppc = __builtin_popcount(t[0]);
			for (int z = t[0]; ; z = (z - 1) & t[0]) {
				ans += (((ppc ^ __builtin_popcount(z)) & 1) ? -1 : 1) * g[t[1] ^ t[0] ^ z];
				if (z == 0) break;
			}
			printf("%d\n", ans);
		} else {
			assert(__builtin_popcount(t[2]) <= K);
			int ans = 0;
			for (int z = t[2]; ; z = (z - 1) & t[2]) {
				ans += a[t[1] | z];
				if (z == 0) break;
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%s", tt);
      |   ~~~~~^~~~~~~~~~

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