oj.uz

Submission #523312

# Submission time Handle Problem Language Result Execution time Memory
523312 2022-02-07T12:21:51 Z sidon Snake Escaping (JOI18_snake_escaping) C++17
5 / 100
 1191 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], id[N];
string A, t[N];
vector<int> g[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 k = 0, p = 1; k < B; ++k, p *= 3)
			id[i] += p * ((48 < t[i][k]) + (62 < t[i][k]));
	}

	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) ans[i] += dp[id[i]];
		}
	}

	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 1120 ms 65092 KB Output is correct
2 Correct 1123 ms 65120 KB Output is correct
3 Correct 1119 ms 65116 KB Output is correct
4 Correct 1165 ms 65108 KB Output is correct
5 Correct 1145 ms 65116 KB Output is correct
6 Correct 1180 ms 65112 KB Output is correct
7 Correct 1151 ms 65112 KB Output is correct
8 Correct 1191 ms 65112 KB Output is correct
9 Correct 1154 ms 65080 KB Output is correct
10 Correct 1138 ms 65120 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1120 ms 65092 KB Output is correct
2 Correct 1123 ms 65120 KB Output is correct
3 Correct 1119 ms 65116 KB Output is correct
4 Correct 1165 ms 65108 KB Output is correct
5 Correct 1145 ms 65116 KB Output is correct
6 Correct 1180 ms 65112 KB Output is correct
7 Correct 1151 ms 65112 KB Output is correct
8 Correct 1191 ms 65112 KB Output is correct
9 Correct 1154 ms 65080 KB Output is correct
10 Correct 1138 ms 65120 KB Output is correct
11 Runtime error 56 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 1120 ms 65092 KB Output is correct
2 Correct 1123 ms 65120 KB Output is correct
3 Correct 1119 ms 65116 KB Output is correct
4 Correct 1165 ms 65108 KB Output is correct
5 Correct 1145 ms 65116 KB Output is correct
6 Correct 1180 ms 65112 KB Output is correct
7 Correct 1151 ms 65112 KB Output is correct
8 Correct 1191 ms 65112 KB Output is correct
9 Correct 1154 ms 65080 KB Output is correct
10 Correct 1138 ms 65120 KB Output is correct
11 Runtime error 56 ms 65540 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1120 ms 65092 KB Output is correct
2 Correct 1123 ms 65120 KB Output is correct
3 Correct 1119 ms 65116 KB Output is correct
4 Correct 1165 ms 65108 KB Output is correct
5 Correct 1145 ms 65116 KB Output is correct
6 Correct 1180 ms 65112 KB Output is correct
7 Correct 1151 ms 65112 KB Output is correct
8 Correct 1191 ms 65112 KB Output is correct
9 Correct 1154 ms 65080 KB Output is correct
10 Correct 1138 ms 65120 KB Output is correct
11 Runtime error 42 ms 65540 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1120 ms 65092 KB Output is correct
2 Correct 1123 ms 65120 KB Output is correct
3 Correct 1119 ms 65116 KB Output is correct
4 Correct 1165 ms 65108 KB Output is correct
5 Correct 1145 ms 65116 KB Output is correct
6 Correct 1180 ms 65112 KB Output is correct
7 Correct 1151 ms 65112 KB Output is correct
8 Correct 1191 ms 65112 KB Output is correct
9 Correct 1154 ms 65080 KB Output is correct
10 Correct 1138 ms 65120 KB Output is correct
11 Runtime error 56 ms 65540 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -