Submission #203005

#	Time	Username	Problem	Language	Result	Execution time	Memory
203005		Noam527	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1089 ms	46680 KiB

snake_escaping

#include <bits/stdc++.h>
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 4e18;
const int OO = 1;
const int OOO = 1;
using namespace std;

/*
Solution idea:
first compute through dp, the values F[mask] = sum(a[S]) for S contained in mask, G[mask] = sum(a[S]) for S contained in mask.
this can be done in O(L * 2^L) (through a nontrivial dp state).
if the string would contain only (0, ?), then the answer is F[mask], mask is binary representation of ?'s.
if the string would contain only (1, ?), same thing but G[mask].

so we use both arrays to cut the time complexity for the general case.
consider the character with minimum frequency in the query string, out of (0, 1, ?). The minimum frequency is between 0 and floor(L / 3).

if the minimum is ?: solve the query naively - try to replace each ? with either 0 or 1
if the minimum is 0: we get rid of 0's, and turn them to 1's and ?'s:
	for the query string x0y (x and y can be any part of the query string), its answer is x?y - x1y.
	once we end up with no 0's (on base cases of this recursive procedure), we can use array G[] as described above.
if the minimum is 1: we turn 1's to 0's and ?'s, in the same manner as above, then use F[].

in all cases we produce 2 possibilities for each character from the lowest frequency, and solve each possibility in O(1), so the complexity is:
time: O(2^L * L + Q * 2^floor(L / 3)).
memory: although the dp has O(2^L * L) states, we eventually only care about the last layer for all queries, so memory is O(2^L).

the problem was very interesting so I decided to write this little description.
the code may not be clear though (and I did not explain the dp); you are welcome to send questions to my codeforces account, Noam527.
*/

const int N = 1 << 20;

int L, L2, q, a[N];
int Z[2][N], O[2][N];

int MP[256] = {};

// cur = binary rep. by 1's
int work_question(int left, int cur) {
	if (!left) return a[cur];
	int x = left & -left;
	return work_question(left ^ x, cur) + work_question(left ^ x, cur ^ x);
}

// gets to 0's.
// cur = binary rep. of ?'s
int work_0(int left, int cur) {
	if (!left) return Z[L & 1][cur];
	int x = left & -left;
	return work_0(left ^ x, cur ^ x) - work_0(left ^ x, cur);
}

// gets to 1's.
// cur = binary rep. of ?'s
int work_1(int left, int cur) {
	if (!left) return O[L & 1][L2 - 1 - cur];
	int x = left & -left;
	return work_1(left ^ x, cur ^ x) - work_1(left ^ x, cur);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	MP['0'] = 0, MP['1'] = 1, MP['?'] = 2;

	cin >> L >> q;
	L2 = (1 << L);
	for (int i = 0; i < L2; i++) {
		char c;
		cin >> c;
		a[i] = c - '0';
		Z[0][i] = O[0][i] = a[i];
	}

	for (int i = 1; i <= L; i++) {
		for (int j = 0; j < L2; j++) {
			int x = j ^ (1 << (i - 1));
			if (j & (1 << (i - 1))) {
				Z[i & 1][j] = Z[i & 1 ^ 1][j] + Z[i & 1 ^ 1][x];
				O[i & 1][j] = O[i & 1 ^ 1][j];
			}
			else {
				Z[i & 1][j] = Z[i & 1 ^ 1][j];
				O[i & 1][j] = O[i & 1 ^ 1][j] + O[i & 1 ^ 1][x];
			}
		}
	}

	while (q--) {
		string s;
		cin >> s;
		int cnt[3] = {}, rep[3] = {};
		for (int i = 0; i < L; i++) {
			cnt[MP[s[i]]]++;
			rep[MP[s[i]]] |= 1 << (L - 1 - i);
		}
		int at = 0;
		if (cnt[1] < cnt[at]) at = 1;
		if (cnt[2] < cnt[at]) at = 2;

		if (at == 2) {
			cout << work_question(rep[at], rep[1]) << '\n';
		}
		else {
			if (at == 0)
				cout << work_1(rep[at], rep[2]) << '\n';
			else
				cout << work_0(rep[at], rep[2]) << '\n';
		}
	}
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:82:23: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     Z[i & 1][j] = Z[i & 1 ^ 1][j] + Z[i & 1 ^ 1][x];
                     ~~^~~
snake_escaping.cpp:82:41: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     Z[i & 1][j] = Z[i & 1 ^ 1][j] + Z[i & 1 ^ 1][x];
                                       ~~^~~
snake_escaping.cpp:83:23: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     O[i & 1][j] = O[i & 1 ^ 1][j];
                     ~~^~~
snake_escaping.cpp:86:23: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     Z[i & 1][j] = Z[i & 1 ^ 1][j];
                     ~~^~~
snake_escaping.cpp:87:23: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     O[i & 1][j] = O[i & 1 ^ 1][j] + O[i & 1 ^ 1][x];
                     ~~^~~
snake_escaping.cpp:87:41: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     O[i & 1][j] = O[i & 1 ^ 1][j] + O[i & 1 ^ 1][x];
                                       ~~^~~
snake_escaping.cpp:97:15: warning: array subscript has type 'char' [-Wchar-subscripts]
    cnt[MP[s[i]]]++;
               ^
snake_escaping.cpp:98:15: warning: array subscript has type 'char' [-Wchar-subscripts]
    rep[MP[s[i]]] |= 1 << (L - 1 - i);
               ^

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