Submission #1255758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255758		mingga	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	988 ms	21788 KiB

snake_escaping

// Author: caption_mingle
#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define ll long long
const int mod = 1e9 + 7;
const int inf = 2e9;
const int N = (1 << 20) + 5;
int l, q, f[N], g[N], a[N];
string s;

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	#define task ""
	if(fopen(task ".INP", "r")) {
		freopen(task ".INP", "r", stdin);
		freopen(task ".OUT", "w", stdout);
	}
	cin >> l >> q;
	cin >> s;
	for(int i = 0; i < sz(s); i++) {
		a[i] = s[i] - '0';
		g[i] = f[i] = a[i];
	}
	for(int i = 0; i < l; i++) {
		for(int mask = 0; mask < (1 << l); mask++) {
			if(mask >> i & 1) f[mask] += f[mask ^ (1 << i)];
			else g[mask] += g[mask ^ (1 << i)];
		}
	}
	for(int i = 1; i <= q; i++) {
		string x; cin >> x;
		reverse(all(x));
		int c0 = 0, c1 = 0;
		vector<int> v0, v1, v2;
		for(int i = 0; i < l; i++) {
			if(x[i] == '0') c0++, v0.pb(i);
			else if(x[i] == '1') c1++, v1.pb(i);
			else v2.pb(i);
		}
		int c2 = l - c0 - c1;
		int ori = 0;
		for(int x : v1) {
			ori ^= (1 << x);
		} 
		int ans = 0;
		if(c2 <= c1 and c2 <= c0) {
			for(int mask = 0; mask < (1 << sz(v2)); mask++) {
				int sub = 0;
				for(int i = 0; i < sz(v2); i++) {
					if(mask >> i & 1) sub ^= (1 << v2[i]);
				}
				ans += a[ori ^ sub];
			}
		} else if(c0 <= c1) {
			for(int mask = 0; mask < (1 << sz(v0)); mask++) {
				int sub = 0;
				for(int i = 0; i < sz(v0); i++) {
					if(mask >> i & 1) sub ^= (1 << v0[i]);
				}
				if(__builtin_popcount(ori ^ sub) & 1) ans += g[ori ^ sub];
				else ans -= g[ori ^ sub];
			}
		} else {
			for(int x : v2) ori ^= (1 << x);
			for(int mask = 0; mask < (1 << sz(v1)); mask++) {
				int sub = 0;
				for(int i = 0; i < sz(v1); i++) {
					if(mask >> i & 1) sub ^= (1 << v1[i]);
				}
				if(__builtin_popcount(ori ^ sub) & 1) ans += f[ori ^ sub];
				else ans -= f[ori ^ sub];
			}
		}
		cout << abs(ans) << ln;
	}
    cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:23:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |                 freopen(task ".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:24:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |                 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