Submission #1211762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211762		witek_cpp	Snake Escaping (JOI18_snake_escaping)	C++20	0 / 100	1 ms	328 KiB

snake_escaping

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

#define st first
#define nd second
#define f(a, c, b) for (int a = c; b > a; a++)
#define pb push_back
#define all(a) a.begin(), a.end()
#define wczytaj(a, c, n) a.resize(n); f(i, c, n) cin >> a[i];
#define sz(a) int(a.size())
#define wypisz(a, c) f(i, c, sz(a)) cout << a[i] << " "; cout << "\n";

int n, q;

vector<int> val;

vector<int> dp;
vector<int> dp2;
vector<int> ile_zapalone;

vector<int> indp;
vector<int> ind1;
vector<int> ind0;

vector<int> wszystkie_maski;
int aktl_maska;
int zmiana;
int p1;

void wygeneruj(int maska, const vector<int>& ind) {
	wszystkie_maski.clear();
	aktl_maska = maska;
	wszystkie_maski.pb(maska);
	f(i, 1, (1 << sz(ind))) {
		zmiana = (i ^ (i - 1));
		p1 = 0;
		while (zmiana & (1 << p1)) {
			aktl_maska ^= (1 << ind[p1]);
			p1++;
		}
		wszystkie_maski.pb(aktl_maska);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> q;
	
	val.resize(1 << n);
	char p1;
	f(i, 0, (1 << n)) {
		cin >> p1;
		val[i] = p1 - '0';
	}
	
	dp.resize(1 << n);
	dp2.resize(1 << n);
	
	f(i, 0, (1 << n)) dp[i] = dp2[i] = val[i];
	
	f(i, 0, n) {
		f(j, 0, (1 << n)) {
			if (j & (1 << i)) {
				dp[j] += dp[j ^ (1 << i)];
			} else {
				dp2[j] += dp2[j ^ (1 << i)];
			}
		}
	}
	
	ile_zapalone.resize(1 << n);
	ile_zapalone[0] = 0;
	int aktl_bit = 0;
	f(i, 1, (1 << n)) {
		if (i == (1 << (aktl_bit + 1))) aktl_bit++;
		ile_zapalone[i] = 1 + ile_zapalone[i ^ (1 << aktl_bit)];
	}
	
	int maska;
	int wnk;
	int p2;
	
	f(_, 0, q) {
		indp.clear();
		ind1.clear();
		ind0.clear();
		maska = 0;
		for (int i = n - 1; i >=0; i--) {
			cin >> p1;
			if (p1 == '?') indp.pb(i);
			else if (p1 == '1') {maska += (1 << i); ind1.pb(i);}
			else ind0.pb(i);
		}
		if (!sz(indp)) {cout << val[maska] << "\n"; continue;}
		wnk =0;
		if (sz(indp) <= (n/3)) {
			wygeneruj(maska, indp);
			for (int ele: wszystkie_maski) wnk += val[ele];
		} else if (sz(ind1) <= (n/3)) {
			maska = 0;
			for (int ele: indp) maska ^= (1 << ele);
			wygeneruj(maska, ind1);
			p2 = ile_zapalone[wszystkie_maski.back()];
			for (int ele: wszystkie_maski) {
				if ((p2 - ile_zapalone[ele])%2 == 0) {
					wnk += dp[ele];
				} else {
					wnk -= dp[ele];
				}
			}
		} else {
			wygeneruj(maska, ind0);
			p2 = ile_zapalone[wszystkie_maski.back()];
			for (int ele: wszystkie_maski) {
				if ((p2 - ile_zapalone[ele])%2 == 0) {
					wnk += dp2[ele];
				} else {
					wnk -= dp2[ele];
				}
			}
		}
		cout << wnk << "\n";
	}
	
	return 0;
}

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