Submission #1290868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290868		Jawad_Akbar_JJ	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1651 ms	21744 KiB

snake_escaping

#include <iostream>

using namespace std;
const int N = 1<<20;
int sub[N], sup[N], cnt[N];
string s, ss;

int main(){
	int l, q, pw[] = {1, -1};
	cin>>l>>q>>s;

	for (int i=0;i<(1<<l);i++){
		sub[i] = sup[i] = s[i] - '0';
		cnt[i] = __builtin_popcount(i);
	}

	for (int i=0;i<l;i++){
		for (int m=0;m<(1<<l);m++)
			if ((1<<i) & m)
				sub[m] += sub[m ^ (1<<i)];
			else
				sup[m] += sup[m ^ (1<<i)];
	}

	for (int i=0;i<q;i++){
		cin>>ss;
		int A = 0, B = 0, C = 0, Ans = 0;
		for (int j=0;j<l;j++){
			if (ss[l - j - 1] == '0')
				A |= (1<<j);
			if (ss[l - j - 1] == '1')
				B |= (1<<j);
			if (ss[l - j - 1] == '?')
				C |= (1<<j);
		}

		if (cnt[C] <= 6){
			Ans = s[B] - '0';
			for (int m = C; m; m = (m - 1) & C)
				Ans += s[m | B] - '0';
		}
		else if (cnt[A] <= 6){
			Ans = sup[B];
			for (int m = A; m; m = (m - 1) & A)
				Ans += sup[B | m] * pw[cnt[m] & 1];
		}
		else{
			Ans = sub[C] * pw[cnt[B] & 1];
			for (int m = B; m; m = (m - 1) & B)
				Ans += sub[C | m] * pw[cnt[B ^ m] & 1];
		}

		cout<<Ans<<'\n';
	}
}

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