Submission #105155

#	Time	Username	Problem	Language	Result	Execution time	Memory
105155		RockyB	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	1901 ms	66560 KiB

snake_escaping

/// In The Name Of God

#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 rep(i, l, r) for (int i = (l); i < (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)

#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)(1 << 20) + 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 L = 7;


int n, q;
char s[N];
char t[N][20];

int add_id;

int tmr;
int was[20][1594323];
int dp[20][1594323];

int a[1594323][13];
ll pw[20];

int last[20];
void rec(int v = 0) {
	if (v == n - L) {
		int mask = 0;
		per(i, n - L - 1, 0) mask = mask * 3 + last[i];
		rep(i, 0, n - L) a[mask][i] = last[i];
		return;
	}
	rep(i, 0, 3) {
		last[v] = i;
		rec(v + 1);
	}
}

inline int calc(int v, int mask, int nmask) {
	if (v == n) {
		return s[nmask + add_id] - '0';
	}
	if (was[v][mask] == tmr) return dp[v][mask];
	was[v][mask] = tmr;
	if (a[mask][v - L] == 2) {
		return dp[v][mask] = calc(v + 1, mask - pw[v - L], nmask + (1 << v)) + calc(v + 1, mask - (pw[v - L] << 1), nmask);
	}
	if (a[mask][v - L] == 1) {
		return dp[v][mask] = calc(v + 1, mask, nmask + (1 << v));
	}
	return dp[v][mask] = calc(v + 1, mask, nmask);
}
/// 3 ^ 0 * q0 + 3 ^ 1 * q1 + 3^2 * q2 = n
/// 7 = 3 ^ 1 * 2 + 3^0 * 1

/*
	3 ^ 2 * q2 + 3 ^ 1 * q1 + 3 ^ 0 * q0
	
*/


int mem[1 << 7][2187];
int hsh[N];
bool good(int mask, int id) {
	if (~mem[mask][hsh[id]]) return mem[mask][hsh[id]];
	rep(i, 0, L) {
		if (t[id][i] != '?') {
			if (t[id][i] == '0' && (mask & (1 << i))) return mem[mask][hsh[id]] = 0;
			if (t[id][i] == '1' && !(mask & (1 << i))) return mem[mask][hsh[id]] = 0;
		}
	}
	return mem[mask][hsh[id]] = 1;
}

int ans[N];
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	Kazakhstan
	cin >> n >> q >> s;
	rep(i, 0, q) {
		cin >> t[i];
		reverse(t[i], t[i] + n);
	}
	L = min(n, L);
	rep(i, 0, q) {
		rep(j, 0, L) {
			if (t[i][j] == '?') hsh[i] = hsh[i] * 3 + 2;
			else if (t[i][j] == '1') hsh[i] = hsh[i] * 3 + 1;
			else hsh[i] = hsh[i] * 3;
		}
	}
	pw[0] = 1;
	rec();
	memset(mem, -1, sizeof(mem));
	rep(i, 1, 20) pw[i] = pw[i - 1] * 3;
	rep(mask, 0, (1 << L)) {
		++tmr;
		rep(i, 0, q) {
			if (good(mask, i)) {
				if (n <= L) {
					ans[i] += s[mask] - '0';
				}
				else {
					int st = 0;
					per(j, n - 1, L) {
						if (t[i][j] == '?') st = st * 3 + 2;
						else if (t[i][j] == '1') st = st * 3 + 1;
						else st *= 3;
					}
					add_id = mask;
					ans[i] += calc(L, st, 0);
				}
			}
		}
	}
	rep(i, 0, q) cout << ans[i] << nl;
	ioi
}

Compilation message (stderr)

snake_escaping.cpp: In function 'bool good(int, int)':
snake_escaping.cpp:97:72: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    if (t[id][i] == '0' && (mask & (1 << i))) return mem[mask][hsh[id]] = 0;
                                                     ~~~~~~~~~~~~~~~~~~~^~~
snake_escaping.cpp:98:73: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    if (t[id][i] == '1' && !(mask & (1 << i))) return mem[mask][hsh[id]] = 0;
                                                      ~~~~~~~~~~~~~~~~~~~^~~
snake_escaping.cpp:101:28: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  return mem[mask][hsh[id]] = 1;
         ~~~~~~~~~~~~~~~~~~~^~~

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