oj.uz

Submission #848697

# Submission time Handle Problem Language Result Execution time Memory
848697 2023-09-13T09:59:55 Z TranGiaHuy1508 Snake Escaping (JOI18_snake_escaping) C++17
0 / 100
 1 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

const int maxn = 1 << 20;

int lg, n, q;
vector<int> v;

vector<int> subsetZeta(vector<int> V){
	for (int j = 0; j < lg; j++){
		for (int i = 0; i < n; i++){
			if (((i >> j) & 1)){
				V[i] += V[i ^ (1 << j)];
			}
		}
	}
	return V;
}

vector<int> supersetZeta(vector<int> V){
	for (int j = 0; j < lg; j++){
		for (int i = 0; i < n; i++){
			if (((i >> j) & 1) == 0){
				V[i] += V[i ^ (1 << j)];
			}
		}
	}
	return V;
}

void main_program(){
	cin >> lg >> q;
	n = 1 << lg;

	v.resize(n);
	string s; cin >> s;
	for (int i = 0; i < n; i++) v[i] = (s[i] - '0');

	vector<int> subset = subsetZeta(v), superset = supersetZeta(v);

	for (int _ = 0; _ < q; _++){
		string Q; cin >> Q;

		int mask0 = 0, mask1 = 0, mask2 = 0;
		for (int i = 0; i < lg; i++){
			if (Q[i] == '0') mask0 |= (1 << (lg-1 - i));
			if (Q[i] == '1') mask1 |= (1 << (lg-1 - i));
			if (Q[i] == '?') mask2 |= (1 << (lg-1 - i));
		}
		int popcnt0 = __builtin_popcount(mask0);
		int popcnt1 = __builtin_popcount(mask1);
		int popcnt2 = __builtin_popcount(mask2);
		int mn = min({popcnt0, popcnt1, popcnt2});

		if (popcnt0 == mn){
			int sum = 0;
			for (int submask = mask0; submask > 0; submask = (submask - 1) & mask2){
				int num = mask1 + submask;
				int sign = ((__builtin_popcount(submask) & 1)) ? -1 : 1;
				sum += superset[num] * sign;
			}
			{
				int submask = 0;
				int num = mask1 + submask;
				int sign = ((__builtin_popcount(submask) & 1)) ? -1 : 1;
				sum += superset[num] * sign;
			}
			cout << sum << "\n";
		}
		else if (popcnt1 == mn){
			int sum = 0;
			for (int submask = mask1; submask > 0; submask = (submask - 1) & mask2){
				int num = mask2 + submask;
				int sign = ((__builtin_popcount(submask) & 1) == (popcnt1 & 1)) ? 1 : -1;
				sum += subset[num] * sign;
			}
			{
				int submask = 0;
				int num = mask2 + submask;
				int sign = ((__builtin_popcount(submask) & 1) == (popcnt1 & 1)) ? 1 : -1;
				sum += subset[num] * sign;
			}
			cout << sum << "\n";
		}
		else{
			int sum = 0;
			for (int submask = mask2; submask > 0; submask = (submask - 1) & mask2){
				int num = mask1 + submask;
				sum += v[num];
			}
			{
				int submask = 0;
				int num = mask1 + submask;
				sum += v[num];
			}
			cout << sum << "\n";
		}
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -