Submission #1301457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301457		KickingKun	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	869 ms	31840 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define ld long double
#define bigint __int128
#define emb emplace_back
#define pb push_back
#define pii pair <int, int>
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define Task ""

#define MASK(k) (1ull << k)
#define bitcnt(k) __builtin_popcount(k)
#define testBit(n, k) ((n >> k) & 1)
#define flipBit(n, k) (n ^ (1ll << k))
#define offBit(n, k) (n & ~MASK(k))
#define onBit(n, k) (n | (1ll << k))

template <class T> bool minimize(T &a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool maximize(T &a, T b) {if (a < b) {a = b; return true;} return false;}

const int N = 2e5 + 5, LG = 20, mod = 1e9 + 7;
const ll INF = 1e18;

int L, q, f[1 << LG], g[1 << LG];
string s;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	if (fopen(Task".inp", "r")) {
		freopen(Task".inp", "r", stdin);
		freopen(Task".out", "w", stdout);
	}

	cin >> L >> q >> s;
	for (int i = 0; i < (1 << L); i++) {
		f[i] = g[((1 << L) - 1) ^ i] = s[i] - 48;
	}

	for (int i = 0; i < L; i++) {
		for (int mask = 0; mask < (1 << L); mask++)
			if (testBit(mask, i)) {
				f[mask] += f[mask ^ (1 << i)];
				g[mask] += g[mask ^ (1 << i)];
			}
	}

	while (q--) {
		string pattern; cin >> pattern;
		int c0 = count(all(pattern), '0');
		int c1 = count(all(pattern), '1');
		int unk = L - c0 - c1;

		if (unk <= 6) {
			vector <int> pos; int initValue = 0;
			for (int i = 0; i < L; i++) {
				if (pattern[L - i - 1] == '?')
					pos.emplace_back(i);
				else initValue += (pattern[L - i - 1] - 48) * (1 << i);
			}

			int ans = 0;
			for (int mask = 0; mask < (1 << unk); mask++) {
				int value = initValue;
				for (int i = 0; i < unk; i++)
					value += testBit(mask, i) * (1 << pos[i]);
				ans += s[value] - 48;
			}
			cout << ans << '\n';
		}

		else if (c1 <= 6) {
			// pattern[i] = 0 -> mask[i] = 1 -> ko lien quan
			// moi mask se duoc anh huong 2^k lan
			// k = so vi tri mask[i] = 0 ma pattern[i] = 1
			// do la nhung lan T[i] = 1 khi mask[i] = pattern[i] = 1
			// va T[i] = 0/1 khi mask[i] = 0 va pattern[i] = 1

			vector <int> S1; int ques = 0;
			for (int i = 0; i < L; i++) {
				if (pattern[L - i - 1] == '1') S1.emplace_back(i);
				if (pattern[L - i - 1] == '?') ques += 1 << i;
			}

			int ans = 0;
			for (int m = 0; m < (1 << c1); m++) {
				int T = 0;
				for (int i = 0; i < c1; i++)
					if (testBit(m, i)) T += 1 << S1[i];
				if ((bitcnt(m) + c1) & 1) ans -= f[T | ques];
				else ans += f[T | ques];
			}
			cout << ans << '\n';
		}

		else {
			// flip 0 -> 1
			vector <int> S0; int ques = 0;
			for (int i = 0; i < L; i++) {
				if (pattern[L - i - 1] == '0') S0.emplace_back(i);
				if (pattern[L - i - 1] == '?') ques += 1 << i;
			}

			int ans = 0;
			for (int m = 0; m < (1 << c0); m++) {
				int T = 0;
				for (int i = 0; i < c0; i++)
					if (testBit(m, i)) T += 1 << S0[i];
				if ((bitcnt(m) + c0) & 1) ans -= g[T | ques];
				else ans += g[T | ques];
			}
			cout << ans << '\n';
		}
	}
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:36:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |                 freopen(Task".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:37:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |                 freopen(Task".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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