Submission #548095

#	Time	Username	Problem	Language	Result	Execution time	Memory
548095		wmch13	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1087 ms	43308 KiB

snake_escaping

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
#define ordered_set tree<pair<ll,int>, null_type,less<pair<ll,int>>, rb_tree_tag,tree_order_statistics_node_update>

const int INF = 1e7;
const ll longINF = 1e17;
const int mxN = 1 << 20;
const int mxM = 1e5 + 9;
const int MOD = 998244353;
const double pi = acos (-1);

void setIO (string s) {
	freopen ((s + ".in").c_str(), "r", stdin);
	freopen ((s + ".out").c_str(), "w", stdout);
	
	return;
}

int sub[mxN], sup[mxN], A[mxN];

bool oddParity (int x) {
	return __builtin_popcount (x) % 2;
}

void solve () {
	int L, Q;
	cin >> L >> Q;
	
	string s;
	cin >> s;
	
	for (int i = 0; i < (1 << L); i++) 
		sub[i] = sup[i] = A[i] = (s[i] - '0');
	
	for (int i = 0; i < L; i++) {
		for (int mask = 0; mask < (1 << L); mask++) {
			if (mask & (1 << i)) {
				sub[mask] += sub[mask ^ (1 << i)];
			} else {
				sup[mask] += sup[mask ^ (1 << i)];
			}
		}
	}
	
	while (Q--) {
		int zero = 0, one = 0, any = 0;
		for (int i = 0; i < L; i++) {
			char c;
			cin >> c;
			
			zero <<= 1;
			one  <<= 1;
			any  <<= 1;
			
			if (c == '0') {
				zero++;
			} else if (c == '1') {
				one++;
			} else any++;
		}
		
		int res = 0;
		if (__builtin_popcount (any) <= 6) {
			for (int mask = any; mask > 0; mask = (mask - 1) & any) 
				res += A[mask | one];
			
			res += A[one];
		} else if (__builtin_popcount (zero) <= 6) {
			for (int mask = zero; mask > 0; mask = (mask - 1) & zero)
				res += sup[mask | one] * (oddParity (mask) ? -1 : 1);
				
			res += sup[one] * (oddParity (0) ? -1 : 1);
		} else {
			for (int mask = one; mask > 0; mask = (mask - 1) & one)
				res += sub[mask | any] * (oddParity (mask ^ one) ? -1 : 1);
			
			res += sub[any] * (oddParity (one) ? -1 : 1);
		}
		
		cout << res << "\n";
	}
	
	return;
}

int main () {
	int t = 1;
	//cin >> t;
	
	ios_base::sync_with_stdio (0);
	cin.tie (0);
	
	//setIO ("deleg");
	//preCalc ();
	while (t--) {
		//initialize common variables
		
		
		//go solve
		solve ();
	}
		
	return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'void setIO(std::string)':
snake_escaping.cpp:25:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  freopen ((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:26:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  freopen ((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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