Submission #675746

#	Time	Username	Problem	Language	Result	Execution time	Memory
675746		MilosMilutinovic	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1578 ms	23200 KiB

snake_escaping

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
	#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

const int N = (1 << 20);
int n, q;
char s[N];
char t[22];
int sub[N];
int sup[N];
vector<int> zero;
vector<int> one;
vector<int> qmark;

char nextChar() {
	char c = getchar();
	while (!isdigit(c) && c != '?') c = getchar();
	return c;
}

int main()
{
	startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	scanf("%d%d", &n, &q);
	for (int i = 0; i < (1 << n); i++)
		s[i] = nextChar();
	for (int i = 0; i < (1 << n); i++) {
		sub[i] = (int)(s[i] - '0');
		sup[i] = (int)(s[i] - '0');
	}
	for (int i = 0; i < n; i++)
		for (int mask = 0; mask < (1 << n); mask++)
			if (mask >> i & 1)
				sub[mask] += sub[mask ^ (1 << i)];
	for (int i = 0; i < n; i++)
		for (int mask = (1 << n) - 1; mask >= 0; mask--)
			if (!(mask >> i & 1))
				sup[mask] += sup[mask ^ (1 << i)];
	int tmask;
	while(q--) {
		for (int i = 0; i < n; i++)
			t[i] = nextChar();
		reverse(t, t + n);
		zero.clear();
		one.clear();
		qmark.clear();
		for (int i = 0; i < n; i++) {
			if (t[i] == '0') zero.push_back(i);
			if (t[i] == '1') one.push_back(i);
			if (t[i] == '?') qmark.push_back(i);
		}
		tmask = 0;
		for (int i = 0; i < n; i++)
			if (t[i] == '1')
				tmask += (1 << i);
		int ans = 0;
		if (qmark.size() <= 6) {
			int sz = qmark.size();
			for (int mask = 0; mask < (1 << sz); mask++) {
				int nmask = tmask;
				for (int i = 0; i < sz; i++)
					if (mask >> i & 1)
						nmask += (1 << qmark[i]);
				ans += (int)(s[nmask] - '0');
			}
		} else if (zero.size() <= 6) {
			int sz = zero.size();
			for (int mask = 0; mask < (1 << sz); mask++) {
				int nmask = tmask;
				for (int i = 0; i < sz; i++)
					if (mask >> i & 1)
						nmask += (1 << zero[i]);
				ans += sup[nmask] * (__builtin_popcount(mask) % 2 == 0 ? 1 : -1);
			}
		} else {
			assert(one.size() <= 6);
			int sz = one.size();
			tmask = 0;
			for (int i = 0; i < n; i++)
				if (t[i] == '?')
					tmask += (1 << i);
			for (int mask = 0; mask < (1 << sz); mask++) {
				int nmask = tmask;
				for (int i = 0; i < sz; i++)
					if (mask >> i & 1)
						nmask += (1 << one[i]);
				ans += sub[nmask] * ((sz - __builtin_popcount(mask)) % 2 == 0 ? 1 : -1);
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~

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