Submission #944361

#	Time	Username	Problem	Language	Result	Execution time	Memory
944361		guechotjrhh	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	729 ms	46344 KiB

snake_escaping

#include<iostream>
#include<string>
using namespace std;
 
#include<string>
#include<vector>
#include<algorithm>
#define maxp 1048580
using namespace std;
int st[maxp],n,p,zer[maxp], on[maxp], cnt[maxp];
int ab(int x) { return x > 0 ? x : -x; }
void init(int N, int Q, char*S){
    n=N; p= 1<<n;
	for (int i = 0; i < p; i++) zer[i] = on[i] = st[i] = S[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];
		}
	}
	cnt[0] = 0;
	for (int i = 0; i < p/2; i++) {
		cnt[i << 1] = cnt[i];
		cnt[(i << 1) + 1] = cnt[i] + 1;
	}
}
 
int query(char* A) {
	int a = 0, b = 0, q = 0, res=0;
	for (int i = 0; i < n; i++) {
		if (A[i] == '0') a|=1<<(n-1-i);
		else if (A[i] == '1') b |= 1 << (n - 1 - i);
		else q |= 1 << (n - 1 - i);
	}
	int oc = cnt[b], zc = cnt[a], qc = cnt[q];
	if (oc < zc && oc < qc) {
		res = 0;
		for (int i = b; i >= 0; i--) {
			i &= b;
			if (cnt[i | q] & 1) res += zer[i | q];
			else res -= zer[i | q];
		}
		res= ab(res);
	}
	else if (qc > zc) {
		res = 0;
		for (int i = a; i >= 0; i--) {
			i &= a;
			if (cnt[i | b] & 1) res += on[i | b];
			else res -= on[i | b];
		}
		res= ab(res);
	}
	else {
		res = 0;
		for (int i = q; i >= 0; i--) {
			i &= q;
			res += st[i | b];
		}
	}
	return res;
}
/*
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; scanf("%d%d", &N, &Q);
	char S[(1<<N)+1]; scanf("%s", S);
	init(N, Q, S);
	for (int i = 0; i < Q; i++) {
		char A[N+1]; scanf("%s", A);
		printf("%d\n", query(A));
	}
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:85:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |  int N, Q; scanf("%d%d", &N, &Q);
      |            ~~~~~^~~~~~~~~~~~~~~~
snake_escaping.cpp:86:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |  char S[(1<<N)+1]; scanf("%s", S);
      |                    ~~~~~^~~~~~~~~
snake_escaping.cpp:89:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   char A[N+1]; scanf("%s", A);
      |                ~~~~~^~~~~~~~~

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