제출 #1228872

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228872		Amaarsaa	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1913 ms	25604 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 < 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];
			else ans -= ta[p];
		}
		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];
			else ans -= na[p];
		}
		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);
	ta.resize(r);
	j = 1<< n;
	for (i =0 ; i < cost.size(); i ++) {
		j --;
		ta[i] = cost[i] - '0';
		na[j] = cost[i] - '0';
	}
	//na

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

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