oj.uz

Submission #105155

# Submission time Handle Problem Language Result Execution time Memory
105155 2019-04-10T18:02:22 Z RockyB Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 1901 ms 66560 KB 
/// 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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 6 ms 1536 KB Output is correct
3 Correct 6 ms 1536 KB Output is correct
4 Correct 7 ms 1536 KB Output is correct
5 Correct 8 ms 1536 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct
7 Correct 7 ms 1536 KB Output is correct
8 Correct 5 ms 1536 KB Output is correct
9 Correct 5 ms 1536 KB Output is correct
10 Correct 5 ms 1536 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 6 ms 1536 KB Output is correct
3 Correct 6 ms 1536 KB Output is correct
4 Correct 7 ms 1536 KB Output is correct
5 Correct 8 ms 1536 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct
7 Correct 7 ms 1536 KB Output is correct
8 Correct 5 ms 1536 KB Output is correct
9 Correct 5 ms 1536 KB Output is correct
10 Correct 5 ms 1536 KB Output is correct
11 Correct 1209 ms 33220 KB Output is correct
12 Correct 1518 ms 32808 KB Output is correct
13 Correct 999 ms 32028 KB Output is correct
14 Correct 1008 ms 32188 KB Output is correct
15 Correct 1449 ms 33176 KB Output is correct
16 Correct 1209 ms 32416 KB Output is correct
17 Correct 1216 ms 32356 KB Output is correct
18 Correct 1277 ms 34256 KB Output is correct
19 Correct 699 ms 31172 KB Output is correct
20 Correct 1548 ms 32868 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 6 ms 1536 KB Output is correct
3 Correct 6 ms 1536 KB Output is correct
4 Correct 7 ms 1536 KB Output is correct
5 Correct 8 ms 1536 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct
7 Correct 7 ms 1536 KB Output is correct
8 Correct 5 ms 1536 KB Output is correct
9 Correct 5 ms 1536 KB Output is correct
10 Correct 5 ms 1536 KB Output is correct
11 Correct 1209 ms 33220 KB Output is correct
12 Correct 1518 ms 32808 KB Output is correct
13 Correct 999 ms 32028 KB Output is correct
14 Correct 1008 ms 32188 KB Output is correct
15 Correct 1449 ms 33176 KB Output is correct
16 Correct 1209 ms 32416 KB Output is correct
17 Correct 1216 ms 32356 KB Output is correct
18 Correct 1277 ms 34256 KB Output is correct
19 Correct 699 ms 31172 KB Output is correct
20 Correct 1548 ms 32868 KB Output is correct
21 Correct 1680 ms 33180 KB Output is correct
22 Correct 1732 ms 33296 KB Output is correct
23 Correct 1120 ms 32684 KB Output is correct
24 Correct 1211 ms 32348 KB Output is correct
25 Correct 1901 ms 34204 KB Output is correct
26 Correct 1220 ms 46204 KB Output is correct
27 Correct 1253 ms 46372 KB Output is correct
28 Correct 1532 ms 48524 KB Output is correct
29 Correct 809 ms 44808 KB Output is correct
30 Correct 1741 ms 46876 KB Output is correct
31 Correct 1548 ms 46752 KB Output is correct
32 Correct 1390 ms 46712 KB Output is correct
33 Correct 887 ms 45608 KB Output is correct
34 Correct 1157 ms 45748 KB Output is correct
35 Correct 1234 ms 46116 KB Output is correct
36 Correct 534 ms 44708 KB Output is correct
37 Correct 1321 ms 46672 KB Output is correct
38 Correct 654 ms 44740 KB Output is correct
39 Correct 1022 ms 46072 KB Output is correct
40 Correct 1187 ms 45816 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 6 ms 1536 KB Output is correct
3 Correct 6 ms 1536 KB Output is correct
4 Correct 7 ms 1536 KB Output is correct
5 Correct 8 ms 1536 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct
7 Correct 7 ms 1536 KB Output is correct
8 Correct 5 ms 1536 KB Output is correct
9 Correct 5 ms 1536 KB Output is correct
10 Correct 5 ms 1536 KB Output is correct
11 Runtime error 73 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 6 ms 1536 KB Output is correct
3 Correct 6 ms 1536 KB Output is correct
4 Correct 7 ms 1536 KB Output is correct
5 Correct 8 ms 1536 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct
7 Correct 7 ms 1536 KB Output is correct
8 Correct 5 ms 1536 KB Output is correct
9 Correct 5 ms 1536 KB Output is correct
10 Correct 5 ms 1536 KB Output is correct
11 Correct 1209 ms 33220 KB Output is correct
12 Correct 1518 ms 32808 KB Output is correct
13 Correct 999 ms 32028 KB Output is correct
14 Correct 1008 ms 32188 KB Output is correct
15 Correct 1449 ms 33176 KB Output is correct
16 Correct 1209 ms 32416 KB Output is correct
17 Correct 1216 ms 32356 KB Output is correct
18 Correct 1277 ms 34256 KB Output is correct
19 Correct 699 ms 31172 KB Output is correct
20 Correct 1548 ms 32868 KB Output is correct
21 Correct 1680 ms 33180 KB Output is correct
22 Correct 1732 ms 33296 KB Output is correct
23 Correct 1120 ms 32684 KB Output is correct
24 Correct 1211 ms 32348 KB Output is correct
25 Correct 1901 ms 34204 KB Output is correct
26 Correct 1220 ms 46204 KB Output is correct
27 Correct 1253 ms 46372 KB Output is correct
28 Correct 1532 ms 48524 KB Output is correct
29 Correct 809 ms 44808 KB Output is correct
30 Correct 1741 ms 46876 KB Output is correct
31 Correct 1548 ms 46752 KB Output is correct
32 Correct 1390 ms 46712 KB Output is correct
33 Correct 887 ms 45608 KB Output is correct
34 Correct 1157 ms 45748 KB Output is correct
35 Correct 1234 ms 46116 KB Output is correct
36 Correct 534 ms 44708 KB Output is correct
37 Correct 1321 ms 46672 KB Output is correct
38 Correct 654 ms 44740 KB Output is correct
39 Correct 1022 ms 46072 KB Output is correct
40 Correct 1187 ms 45816 KB Output is correct
41 Runtime error 73 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Halted 0 ms 0 KB -