제출 #203003

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
203003		Noam527	Snake Escaping (JOI18_snake_escaping)	C++17	75 / 100	2003 ms	48720 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];

inline int zero(int mask) {
	return Z[L & 1][mask];
}
inline int one(int mask) {
	return O[L & 1][mask];
}

// cur = binary rep. by 1's
int work_question(const vector<int> &ind, int nxt, int cur) {
	if (nxt == ind.size()) return a[cur];
	return work_question(ind, nxt + 1, cur) + work_question(ind, nxt + 1, cur | (1 << ind[nxt]));
}

// gets to 0's.
// cur = binary rep. of ?'s
int work_0(const vector<int> &ind, int nxt, int cur) {
	if (nxt == ind.size()) return zero(cur);
	return work_0(ind, nxt + 1, cur | (1 << ind[nxt])) - work_0(ind, nxt + 1, cur);
}

// gets to 1's.
// cur = binary rep. of ?'s
int work_1(const vector<int> &ind, int nxt, int cur) {
	if (nxt == ind.size()) return one(L2 - 1 - cur);
	return work_1(ind, nxt + 1, cur | (1 << ind[nxt])) - work_1(ind, nxt + 1, cur);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	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;
		vector<int> pos[3];
		for (int i = 0; i < L; i++) {
			if (s[i] == '0')
				pos[0].push_back(L - 1 - i);
			else if (s[i] == '1')
				pos[1].push_back(L - 1 - i);
			else
				pos[2].push_back(L - 1 - i);
		}
		int at = 0;
		if (pos[1].size() < pos[at].size()) at = 1;
		if (pos[2].size() < pos[at].size()) at = 2;

		if (at == 2) {
			int cur = 0;
			for (int i = 0; i < L; i++)
				if (s[i] == '1')
					cur |= 1 << (L - 1 - i);
			cout << work_question(pos[at], 0, cur) << '\n';
		}
		else {
			int cur = 0;
			for (int i = 0; i < L; i++)
				if (s[i] == '?')
					cur |= 1 << (L - 1 - i);
			if (at == 0)
				cout << work_1(pos[at], 0, cur) << '\n';
			else
				cout << work_0(pos[at], 0, cur) << '\n';
		}
	}
}

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

snake_escaping.cpp: In function 'int work_question(const std::vector<int>&, int, int)':
snake_escaping.cpp:49:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (nxt == ind.size()) return a[cur];
      ~~~~^~~~~~~~~~~~~
snake_escaping.cpp: In function 'int work_0(const std::vector<int>&, int, int)':
snake_escaping.cpp:56:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (nxt == ind.size()) return zero(cur);
      ~~~~^~~~~~~~~~~~~
snake_escaping.cpp: In function 'int work_1(const std::vector<int>&, int, int)':
snake_escaping.cpp:63:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (nxt == ind.size()) return one(L2 - 1 - cur);
      ~~~~^~~~~~~~~~~~~
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];
                                       ~~^~~

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