Submission #651528

#	Time	Username	Problem	Language	Result	Execution time	Memory
651528		ymm	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1688 ms	46268 KiB

snake_escaping

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int L = 20;
int sub[1<<L];
int sup[1<<L];
int poi[1<<L];
int sign[1<<L];
int q, l;

void sos()
{
	Loop (i,0,1<<l) {
		sign[i] = __builtin_popcount(i)&1? -1: 1;
		sub[i] = poi[i];
		sup[i] = poi[i];
	}
	for (int i = 1; i < (1<<l); i <<= 1) {
		Loop (j,0,1<<l) {
			if (j&i) {
				sub[j] += sub[j^i];
				sup[j^i] += sup[j];
			}
		}
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> l >> q;
	Loop (i,0,1<<l) {
		char c;
		cin >> c;
		poi[i] = c-'0';
	}
	sos();
	while (q--) {
		int cnt[3]={}, msk[3]={};
		LoopR (i,0,l) {
			char c;
			cin >> c;
			c = c =='?'? 2: c-'0';
			cnt[c]++;
			msk[c] ^= (1<<i);
		}
		int ans = 0;
		if (cnt[2] <= cnt[0] && cnt[2] <= cnt[0]) {
			int x = msk[2];
			Loop (i,0,1<<cnt[2]) {
				ans += poi[msk[1] ^ x];
				x = (x-1) & msk[2];
			}
		} else if (cnt[1] <= cnt[0] && cnt[1] <= cnt[2]) {
			int x = msk[1];
			Loop (i,0,1<<cnt[1]) {
				ans += sub[msk[2] ^ x] * sign[msk[1] ^ x];
				x = (x-1) & msk[1];
			}
		} else {
			int x = msk[0];
			Loop (i,0,1<<cnt[0]) {
				ans += sup[msk[1] ^ x] * sign[x];
				x = (x-1) & msk[0];
			}
		}
		cout << ans << '\n';
	}
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:49:8: warning: array subscript has type 'char' [-Wchar-subscripts]
   49 |    cnt[c]++;
      |        ^
snake_escaping.cpp:50:8: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |    msk[c] ^= (1<<i);
      |        ^

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