Submission #41149

#	Time	Username	Problem	Language	Result	Execution time	Memory
41149		kriii	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1012 ms	21820 KiB

snake_escaping

#include <stdio.h>
#include <algorithm>
using namespace std;

int L,Q;
char sc[1<<20+2]; int bc[1<<20];
int Z[1<<20],O[1<<20];
 
void go(int l, int r)
{
	if (l+1 == r) return;
 
	int m = (l + r) / 2;
	go(l,m);
	go(m,r);
	for (int i=l;i<m;i++){
		Z[i-l+m] += Z[i];
		O[i] += O[i-l+m];
	}
}
 
int main()
{
	scanf ("%d %d",&L,&Q);
	scanf ("%s",sc);
 
	for (int i=0;i<(1<<L);i++){
		if (i) bc[i] = bc[i-(i&(-i))] + 1;
		Z[i] = O[i] = sc[i] - '0';
	}
	go(0,(1<<L));
 
	while (Q--){
		char q[22]; scanf ("%s",q);
		int z = 0, o = 0, f = 0;
		for (int i=0;i<L;i++){
			if (q[i] == '0') z |= 1 << (L - i - 1);
			if (q[i] == '1') o |= 1 << (L - i - 1);
			if (q[i] == '?') f |= 1 << (L - i - 1);
		}
		int m = min({bc[z],bc[o],bc[f]});
		int ans = 0;
		if (bc[f] == m){
			for (int x=f;;x=(x-1)&f){
				ans += sc[x|o] - '0';
				if (!x) break;
			}
		}
		else if (bc[o] == m){
			for (int x=o;;x=(x-1)&o){
				int b = f + x;
				if (bc[o] % 2 != bc[x] % 2) ans -= Z[b];
				else ans += Z[b];
				if (!x) break;
			}
		}
		else{
			for (int x=z;;x=(x-1)&z){
				int b = o + z - x;
				if (bc[z] % 2 != bc[x] % 2) ans -= O[b];
				else ans += O[b];
				if (!x) break;
			}
		}
		printf ("%d\n",ans);
	}
	return 0;
}

Compilation message (stderr)

snake_escaping.cpp:6:10: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
 char sc[1<<20+2]; int bc[1<<20];
          ^
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:24:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d",&L,&Q);
                       ^
snake_escaping.cpp:25:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%s",sc);
                 ^
snake_escaping.cpp:34:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char q[22]; scanf ("%s",q);
                             ^

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