Submission #41362

#	Time	Username	Problem	Language	Result	Execution time	Memory
41362		RockyB	Snake Escaping (JOI18_snake_escaping)	C++14	0 / 100	1 ms	128 KiB

snake_escaping

/// In The Name Of God

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)5e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;

const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;


int n, q;
int a[N];

int now[N];
int dp1[1 << 27];

int bp(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1) res *= x;
		x *= x, y >>= 1;
	}
	return res;
}
int p[N];
int rec1(int v = 0, int mask = 0) {
	if (v == n) return a[mask];
	if (p[v] < 2) return rec1(v + 1, mask | (1 << v) * p[v]);
	int res = 0;
	for (int i = 0; i <= 1; i++) {
		res += rec1(v + 1, mask | (1 << v) * i);
	}
	return res;
}
void rec(int v = 0, int now = 0) {
	if (v == n) {
		dp1[now] += rec1();
		return;
	}
	for (int i = 0; i <= 2; i++) {
		p[v] = i;
		rec(v + 1, now + bp(3, v) * i);
	}
}
void solve() {
	int mask = 0;
	for (int i = n - 1; i >= 0; i--) {
		char x;
		cin >> x;
		if (x == '?') now[i] = 2;
		else now[i] = x - '0';
		mask += now[i] * bp(3, i);
	}
	cout << dp1[mask] << nl;
}
int32_t main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	//Kazakhstan
	cin >> n >> q;
	for (int i = 0, j = (1 << n); i < j; i++) {
		char x;
		cin >> x;
		a[i] = x - '0';
	}
	rec();
	for (int i = 1; i <= q; i++) {
		solve();
	}
	ioi
}

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