Submission #1129702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129702		am_aadvik	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	1373 ms	31840 KiB

snake_escaping

#include <iostream>
#include <vector>
#include <queue>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <cstring>
#include <string>
#define int long long
const int inf = 1e17;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 5;
const int maxn2 = 1e5 + 5;
const int maxs = 1e3 + 5;
const int maxl = 2e3 + 5;
const int sz = 1594324;
using namespace std;

int dp[sz], log3[sz], a[sz];
int sol(int val) {
	if (dp[val]) return dp[val];

	int pos = 0, n = val, b = 0;
	while (n) {
		if ((n % 3) == 2) break;
		b += (pow(2, pos) * (n % 3));
		pos++, n /= 3;
	}

	if (n == 0) return a[b];

	int sub = pow(3, pos);
	return dp[val] = sol(val - sub) + sol(val - (2 * sub));
}

void problemA() {
	for (int i = 1; i < sz; ++i) log3[i] = log3[i / 3] + 1;

	int n, q; string s;
	cin >> n >> q >> s;
	for (int i = 0; i < (1 << n); ++i)
		a[i] = (s[i] - '0');

	while (q--) {
		cin >> s;
		int val = 0, p = 1;
		for (int i = n - 1; i >= 0; --i) {
			if (s[i] == '?') val += (p * 2);
			else val += ((s[i] - '0') * p);
			p *= 3;
		}
		cout << sol(val) << endl;
	}
}

void problemB() {
	int n, mx = 0;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; mx = max(a[i], mx), ++i)
		cin >> a[i];
	if (n == 1) cout << a[0];
	else if (n == 2) cout << a[0] + a[1];
	else if (n == 3) {
		int c1 = (mx * 3ll);
		int f1 = a[0] * 3ll;
		int f2 = (a[1] * 2ll);
		int c2 = f1 + f2 + a[2];
		f1 = max(a[1], a[2]);
		f1 += a[0];
		f1 *= 2ll;
		int c3 = a[0] + f1;
		f1 = max(a[0], a[1]);
		f1 *= 3ll;
		int c4 = f1 + a[2];
		cout << min({ c1, c2, c3, c4 });
	}
	else
		cout << mx * n;
}

bool isin(int l, int r, int i) { return ((l <= i) && (i <= r)); }
vector<vector<int>> g[maxn2];
bool vis[maxn2];

bool dfs(int node, int sink, int e) {
	if (node == sink) return 1;
	vis[node] = 1;
	for (auto x : g[node])
		if (!vis[x[0]] && (isin(x[1], x[2], e)))
			if (dfs(x[0], sink, e))
				return 1;
	return 0;
}

void problemC() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int u, v, o, c;
		cin >> u >> v >> o >> c;
		g[u].push_back({ v, o, c });
		g[v].push_back({ u, o, c });
	}

	int q;
	cin >> q;
	while (q--) {
		int u, v, t;
		cin >> u >> v >> t;
		cout << (dfs(u, v, t) ? "YES" : "NO") << endl;
		for (int i = 0; i < n; ++i) vis[i] = 0;
	}
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t = 1;
	while (t--) {
		problemA();
	}
}

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