oj.uz

Submission #523314

# Submission time Handle Problem Language Result Execution time Memory
523314 2022-02-07T12:26:02 Z sidon Snake Escaping (JOI18_snake_escaping) C++17
58 / 100
 1383 ms 65540 KB 
#include <bits/stdc++.h>
using namespace std;

const int B = 13, N = 1<<20, SZ = pow(3, B);

int Q, dp[SZ], ans[N];
string A, t[N];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> Q >> Q >> A;
	A.resize(N, '0');

	for(int i = 0; i < Q; ++i) {
		cin >> t[i];
		reverse(begin(t[i]), end(t[i]));
		t[i].resize(20, '0');
	}

	for(int s = 0; s < (1<<(20-B)); ++s) {
		memset(dp, 0, sizeof dp);

		for(int i = 0; i < (1<<B); ++i) {
			int j = 0;
			for(int k = 0, p = 1; k < B; ++k, p *= 3)
				if(i & (1<<k)) j += p;

			dp[j] += A[i | (s << B)] - '0';
		}

		for(int i = 1; i < SZ; ++i) {
			int j = -1, pw = 1;

			for(int k = 0, p = i; k < B; ++k, p /= 3, pw *= 3)
				if((p % 3) > 1) j = k, k = B;
			
			if(j >= 0)
				pw /= 3, dp[i] = dp[i - pw] + dp[i - 2 * pw];
		}


		for(int i = 0; i < Q; ++i) {
			bool OK = 1;
			for(int k = 0; k < (20-B); ++k)
				if(t[i][B+k] != '?' && bool(s & (1<<k)) != (t[i][B+k] - '0'))
					OK = 0;
			if(OK) {
				int id = 0;
				for(int k = 0, p = 1; k < B; ++k, p *= 3)
					id += p * ((48 < t[i][k]) + (62 < t[i][k]));
				ans[i] += dp[id];
			}
		}
	}

	for(int i = 0; i < Q; ++i)
		cout << ans[i] << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1051 ms 40468 KB Output is correct
2 Correct 1022 ms 40464 KB Output is correct
3 Correct 1070 ms 40468 KB Output is correct
4 Correct 1022 ms 40572 KB Output is correct
5 Correct 1038 ms 40484 KB Output is correct
6 Correct 1004 ms 40500 KB Output is correct
7 Correct 1057 ms 40472 KB Output is correct
8 Correct 1022 ms 40464 KB Output is correct
9 Correct 1061 ms 40460 KB Output is correct
10 Correct 1006 ms 40468 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1051 ms 40468 KB Output is correct
2 Correct 1022 ms 40464 KB Output is correct
3 Correct 1070 ms 40468 KB Output is correct
4 Correct 1022 ms 40572 KB Output is correct
5 Correct 1038 ms 40484 KB Output is correct
6 Correct 1004 ms 40500 KB Output is correct
7 Correct 1057 ms 40472 KB Output is correct
8 Correct 1022 ms 40464 KB Output is correct
9 Correct 1061 ms 40460 KB Output is correct
10 Correct 1006 ms 40468 KB Output is correct
11 Runtime error 122 ms 65540 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1051 ms 40468 KB Output is correct
2 Correct 1022 ms 40464 KB Output is correct
3 Correct 1070 ms 40468 KB Output is correct
4 Correct 1022 ms 40572 KB Output is correct
5 Correct 1038 ms 40484 KB Output is correct
6 Correct 1004 ms 40500 KB Output is correct
7 Correct 1057 ms 40472 KB Output is correct
8 Correct 1022 ms 40464 KB Output is correct
9 Correct 1061 ms 40460 KB Output is correct
10 Correct 1006 ms 40468 KB Output is correct
11 Runtime error 122 ms 65540 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1051 ms 40468 KB Output is correct
2 Correct 1022 ms 40464 KB Output is correct
3 Correct 1070 ms 40468 KB Output is correct
4 Correct 1022 ms 40572 KB Output is correct
5 Correct 1038 ms 40484 KB Output is correct
6 Correct 1004 ms 40500 KB Output is correct
7 Correct 1057 ms 40472 KB Output is correct
8 Correct 1022 ms 40464 KB Output is correct
9 Correct 1061 ms 40460 KB Output is correct
10 Correct 1006 ms 40468 KB Output is correct
11 Correct 1310 ms 43096 KB Output is correct
12 Correct 1383 ms 43220 KB Output is correct
13 Correct 1231 ms 43092 KB Output is correct
14 Correct 1300 ms 43092 KB Output is correct
15 Correct 1279 ms 43216 KB Output is correct
16 Correct 1280 ms 43184 KB Output is correct
17 Correct 1251 ms 43096 KB Output is correct
18 Correct 1187 ms 43348 KB Output is correct
19 Correct 1089 ms 42960 KB Output is correct
20 Correct 1355 ms 43216 KB Output is correct
21 Correct 1297 ms 43116 KB Output is correct
22 Correct 1304 ms 43092 KB Output is correct
23 Correct 1168 ms 43092 KB Output is correct
24 Correct 1287 ms 43088 KB Output is correct
25 Correct 1251 ms 43204 KB Output is correct
26 Correct 1074 ms 43020 KB Output is correct
27 Correct 1283 ms 43092 KB Output is correct
28 Correct 1189 ms 42964 KB Output is correct
29 Correct 1226 ms 43096 KB Output is correct
30 Correct 1246 ms 43088 KB Output is correct
31 Correct 1202 ms 43072 KB Output is correct
32 Correct 1284 ms 43096 KB Output is correct
33 Correct 1220 ms 43092 KB Output is correct
34 Correct 1063 ms 42980 KB Output is correct
35 Correct 1223 ms 43088 KB Output is correct
36 Correct 1206 ms 43168 KB Output is correct
37 Correct 1227 ms 43092 KB Output is correct
38 Correct 1204 ms 43048 KB Output is correct
39 Correct 1211 ms 43108 KB Output is correct
40 Correct 1268 ms 43164 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1051 ms 40468 KB Output is correct
2 Correct 1022 ms 40464 KB Output is correct
3 Correct 1070 ms 40468 KB Output is correct
4 Correct 1022 ms 40572 KB Output is correct
5 Correct 1038 ms 40484 KB Output is correct
6 Correct 1004 ms 40500 KB Output is correct
7 Correct 1057 ms 40472 KB Output is correct
8 Correct 1022 ms 40464 KB Output is correct
9 Correct 1061 ms 40460 KB Output is correct
10 Correct 1006 ms 40468 KB Output is correct
11 Runtime error 122 ms 65540 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -