Submission #1228868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228868		Amaarsaa	Snake Escaping (JOI18_snake_escaping)	C++20	22 / 100	1577 ms	131072 KiB

snake_escaping

#include<bits/stdc++.h>

using namespace std;
using ll = int;
const ll N = 1<<20 + 2;
const ll LOG = 22;
string cost;
ll n;
vector < vector < int > > na, ta;
void Solve() {
	ll ans, s, p, r, i, cnt, j, Neg, Teg;
	string str;
	
	cin >> str;
	
	vector < ll > asuult , neg, teg;
	
	r = 1<< (n- 1);
	for (i = 0; i < str.size(); i ++) {
		if ( str[i] == '?') asuult.push_back(r);
		if ( str[i] == '0') teg.push_back(r);
		if ( str[i] == '1') neg.push_back(r);
		r/= 2;
	}
	if ( asuult.size() <= 6) {
		s =0;
		for (i =0 ; i < neg.size(); i++) s += neg[i];
		
		ans =0;
		for ( i = 0; i < (1<<(asuult.size())); i ++) {
			p =s;
			for (j =0 ;  j< asuult.size(); j ++) {
				r = i & (1<<j);
				if ( r != 0) p += asuult[j];
			}
			ans += (cost[p] - '0');
		}
		
		cout << ans << endl;
		return ;
	}
	
	if ( neg.size() <= 6) {
		Neg = neg.size(); 
		s =0;
		for (i =0 ; i < asuult.size(); i++) s += asuult[i];
		ans =0;
		for (i = 0; i < (1<< Neg); i++){
			p = s;
			cnt =0 ;
			for (j = 0; j < Neg; j ++) {
				r = (i) & (1<< j);
				if ( r != 0) {
					p = p + neg[j];
				}
				else cnt ++;
			}
			if ( cnt % 2 == 0) ans += ta[p][n];
			else ans -= ta[p][n];
		}
		cout << ans << endl;
		return ;
	}
	if ( teg.size() <= 6) {
		Teg = teg.size(); 
		s =0;
		for (i =0 ; i < asuult.size(); i++) s += asuult[i];
		ans =0;
		for (i = 0; i < (1<< Teg); i++){
			p = s;
			cnt =0 ;
			for (j = 0; j < Teg; j ++) {
				r = (i) & (1<< j);
				if ( r != 0) {
					p = p + teg[j];
				}
				else cnt ++;
			}
			if ( cnt % 2 == 0) ans += na[p][n];
			else ans -= na[p][n];
		}
		cout << ans << endl;
		return ;
	}
	
}



int main() {
	ll q, p, r, i, i1, j;
	
	cin >> n >> q;
	
	cin >> cost;

	// precomp
	r = (1<< n);
	na.resize(r, vector < int > (n + 1, 0));
	ta.resize(r, vector < int > (n + 1, 0));
	j = 1<< n;
	for (i =0 ; i < cost.size(); i ++) {
		j --;
		ta[i][0] = cost[i] - '0';
		na[j][0] = cost[i] - '0';
	}
	//na

	
	for (i = 0; i < r; i ++) {
		for (j = 1; j <= n; j ++) {
			p = i & (1<< (n - j));
			if ( p != 0) {
				i1 = i ^ (1<<(n - j));
				na[i][j] = na[i][j - 1] + na[i1][j- 1];
			}
			else na[i][j] = na[i][j- 1];
		}
	}
	// ta
	r = (1<< n);
	for (i = 0; i < r; i ++) {
		for (j = 1; j <= n; j ++) {
			p = i & (1<< (n - j));
			if ( p != 0) {
				i1 = i ^ (1<<(n - j));
				ta[i][j] = ta[i][j - 1] + ta[i1][j- 1];
			}
			else ta[i][j] = ta[i][j- 1];
		}
	}	
	
	while (q --) {
		Solve();
	}
}

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