Submission #943787

#	Time	Username	Problem	Language	Result	Execution time	Memory
943787		guechotjrhh	Snake Escaping (JOI18_snake_escaping)	C++14	75 / 100	2020 ms	19220 KiB

snake_escaping

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

#include<map>
#include<string>
#include<vector>
#define maxp 1048580
using namespace std;
string str;
int st[maxp],n,p,res,zer[maxp], on[maxp];
int ab(int x) { return x > 0 ? x : -x; }
void init(int N, int Q, string S) {
	n = N; p = 1 << n; str = S;
	for (int i = 0; i < p; i++) zer[i] = on[i] = st[i] = str[i] - '0';
	for (int i = 1; i < p; i<<=1) {
		for (int j = 0; j < p; j++) {
			if (j & i) zer[j] += zer[j ^ i];
			else on[j] += on[j ^ i];
		}
	}
}
void rec1(vector<int>& o, int i, int c, int a, int b) {
	if (i == o.size()) {res += (a^zer[c]) + b;return;}
	rec1(o, i + 1, c, a, b);
	rec1(o, i + 1, c ^ o[i], ~a, 1-b);
}
void rec0(vector<int>& z, int i, int c, int a, int b) {
	if (i == z.size()) {res += (a^on[c]) + b;return;}
	rec0(z, i + 1, c, a, b);
	rec0(z, i + 1, c ^ z[i], ~a, 1-b);
}
void recq(vector<int>& q, int i, int c) {
	if (i == q.size()) { res += st[c]; return; }
	recq(q, i + 1, c);
	recq(q, i + 1, c ^ q[i]);
}
int query(string A) {
	int zc = 0, oc = 0, qc = 0;
	for (int i = 0; i < n; i++) {
		if (A[i] == '0') zc++;
		else if (A[i] == '1') oc++;
		else qc++;
	}
	if (oc < zc && oc < qc) {
		int c = 0;
		vector<int> o;
		for (int i = 0; i < n; i++) {
			if (A[i] == '1') o.push_back(1 << (n - 1 - i));
			else if(A[i]=='?') c += (1 << (n - 1 - i));
		}
		res = 0;
		rec1(o, 0, c, 0, 0);
		return ab(res);
	}
	else if (qc > zc) {
		int c = 0;
		vector<int> z;
		for (int i = 0; i < n; i++) {
			if (A[i] == '1') c += (1 << (n - 1 - i));
			else if (A[i] == '0') z.push_back(1 << (n - 1 - i));
		}
		res = 0;
		rec0(z, 0, c, 0, 0);
		return ab(res);
	}
	else {
		res = 0;
		int c = 0;
		vector<int> q;
		for (int i = 0; i < n; i++) {
			if (A[i] == '1') c += (1 << (n - 1 - i));
			else if (A[i] == '?') q.push_back(1 << (n - 1 - i));
		}
		recq(q, 0, c);
		return res;
	}
	return 0;
}
/*
4 8
3141592653589793
0101
?01?
??1?
?0??
1?00
01?1
??10
????

3 5
12345678
000
0??
1?0
?11
???
*/
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 'void rec1(std::vector<int>&, int, int, int, int)':
snake_escaping.cpp:24:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  if (i == o.size()) {res += (a^zer[c]) + b;return;}
      |      ~~^~~~~~~~~~~
snake_escaping.cpp: In function 'void rec0(std::vector<int>&, int, int, int, int)':
snake_escaping.cpp:29:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  if (i == z.size()) {res += (a^on[c]) + b;return;}
      |      ~~^~~~~~~~~~~
snake_escaping.cpp: In function 'void recq(std::vector<int>&, int, int)':
snake_escaping.cpp:34:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  if (i == q.size()) { res += st[c]; return; }
      |      ~~^~~~~~~~~~~

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