Submission #943707

#	Time	Username	Problem	Language	Result	Execution time	Memory
943707		guechotjrhh	Snake Escaping (JOI18_snake_escaping)	C++14	12 / 100	2057 ms	20316 KiB

snake_escaping

#include<iostream>
#include<string>
using namespace std;

#include<map>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
#define all(x) x.begin(),x.end()
string str;
int n,p;
vector<int> zer, on;//sum of those i contains, sum of those contains me i
void init(int N, int Q, string S) {
	n = N; p = 1 << n;
	str = S;
	zer.resize(p); on.resize(p);
	for (int i = 0; i < p; i++) zer[i] = on[i] = S[i] - '0';
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < p; j++) {
			if (j & (1 << i)) zer[j] += zer[j - (1 << i)];
			else on[j] += on[j + (1 << i)];
		}
	}
	//for (int i = 0; i < p; i++) cout << i << ' ' << zer[i] << endl;
	//for (int i = 0; i < p; i++) cout << i << ' ' << on[i] << endl;
}
int ab(int x) { return x > 0 ? x : -x; }
int query(string A) {
	vector<int> ze, o, q;
	for (int i = 0; i < n; i++) {
		if (A[i] == '0') ze.push_back(n-1-i);
		else if (A[i] == '1') o.push_back(n-1-i);
		else q.push_back(n-1-i);
	}
	if (ze.size() > o.size()) {
		int c = 0;
		for (int i : q) c += 1 << i;
		int res = 0;
		for (int i = 0; i < (1 << o.size()); i++) {
			int w = c, x=0;
			for (int j = 0; j < o.size(); j++) {
				if (i & (1 << j)) {
					w += 1 << o[j];
					x++;
				}
			}
			if (x & 1) res += zer[w];
			else res -= zer[w];
		}
		return ab(res);
	}
	else {
		int c = 0;
		for (int i : o) c += 1 << i;
		int res = 0;
		for (int i = 0; i < (1 << ze.size()); i++) {
			int w = c, x = 0;
			for (int j = 0; j < ze.size(); j++) {
				if (i & (1 << j)) {
					w += 1 << ze[j];
					x++;
				}
			}
			if (x & 1) res += on[w];
			else res -= on[w];
		}
		return ab(res);
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, Q; cin >> N >> Q;
	string S; cin >> S;
	init(N, Q, move(S));
	
	for (int i = 0; i < Q; i++) {
		string A;
		cin >> A;
		cout << query(move(A)) << endl;
	}
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int query(std::string)':
snake_escaping.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    for (int j = 0; j < o.size(); j++) {
      |                    ~~^~~~~~~~~~
snake_escaping.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    for (int j = 0; j < ze.size(); j++) {
      |                    ~~^~~~~~~~~~~

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