oj.uz

Submission #41158

# Submission time Handle Problem Language Result Execution time Memory
41158 2018-02-13T07:03:29 Z aome Snake Escaping (JOI18_snake_escaping) C++14
58 / 100
 2000 ms 24288 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1000005;
const int M = 531441; // 3 ^ 12

int n, q;
int to3[1 << 12];
int mask2[2][N]; // 0 check and, 1 check or
int mask3[N];
int res[N];
int pw3[12], f[M], g[M];
string a;

void prepare() {
	for (int i = 0; i < (1 << 12); ++i) {
		for (int j = 11; j >= 0; --j) {
			to3[i] *= 3;
			if (i >> j & 1) to3[i]++;
		}
	}
	pw3[0] = 1; 
	for (int i = 1; i < 12; ++i) pw3[i] = 3 * pw3[i - 1];
	for (int i = 0; i < M; ++i) {
		int cur = i;
		g[i] = -1;
		for (int j = 0; j < 12; ++j) {
			if (cur % 3 == 2) g[i] = j;
			cur /= 3;
		}
	}
}

void calc() {
	for (int i = 0; i < M; ++i) {
		if (g[i] != -1) {
			f[i] += f[i - 2 * pw3[g[i]]];
			f[i] += f[i - 1 * pw3[g[i]]];
		}
	}
}

inline bool check(int mask, int i) {
	return (mask & mask2[0][i]) == mask2[0][i] && (mask | mask2[1][i]) == mask2[1][i];
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> q >> a; 
	for (int i = 0; i < q; ++i) {
		string s; cin >> s;
		for (int j = max(0, n - 8); j < n; ++j) { // first 8 bits
			mask2[0][i] <<= 1, mask2[1][i] <<= 1;
			if (s[j] == '1') mask2[0][i]++;
			if (s[j] == '?' || s[j] == '1') mask2[1][i]++;
		}
		for (int j = 0; j < max(0, n - 8); ++j) { // last 12 bits
			mask3[i] *= 3;
			if (s[j] == '1') mask3[i]++;
			if (s[j] == '?') mask3[i] += 2;
		}
	}
	prepare();
	for (int i = 0; i < 256; ++i) { // first 8 bits
		memset(f, 0, sizeof f);
		for (int j = 0; j < (1 << max(0, n - 8)); ++j) {
			f[to3[j]] += a[j << 8 | i] - '0';
		}
		calc();
		for (int j = 0; j < q; ++j) {
			if (!check(i, j)) continue;
			res[j] += f[mask3[j]];
		}
	}
	for (int i = 0; i < q; ++i) printf("%d\n", res[i]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 4604 KB Output is correct
2 Correct 368 ms 4656 KB Output is correct
3 Correct 381 ms 4692 KB Output is correct
4 Correct 439 ms 4800 KB Output is correct
5 Correct 378 ms 4812 KB Output is correct
6 Correct 371 ms 4828 KB Output is correct
7 Correct 392 ms 4828 KB Output is correct
8 Correct 399 ms 4828 KB Output is correct
9 Correct 408 ms 4884 KB Output is correct
10 Correct 384 ms 4884 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 4604 KB Output is correct
2 Correct 368 ms 4656 KB Output is correct
3 Correct 381 ms 4692 KB Output is correct
4 Correct 439 ms 4800 KB Output is correct
5 Correct 378 ms 4812 KB Output is correct
6 Correct 371 ms 4828 KB Output is correct
7 Correct 392 ms 4828 KB Output is correct
8 Correct 399 ms 4828 KB Output is correct
9 Correct 408 ms 4884 KB Output is correct
10 Correct 384 ms 4884 KB Output is correct
11 Correct 1197 ms 24288 KB Output is correct
12 Correct 1426 ms 24288 KB Output is correct
13 Execution timed out 2021 ms 24288 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 4604 KB Output is correct
2 Correct 368 ms 4656 KB Output is correct
3 Correct 381 ms 4692 KB Output is correct
4 Correct 439 ms 4800 KB Output is correct
5 Correct 378 ms 4812 KB Output is correct
6 Correct 371 ms 4828 KB Output is correct
7 Correct 392 ms 4828 KB Output is correct
8 Correct 399 ms 4828 KB Output is correct
9 Correct 408 ms 4884 KB Output is correct
10 Correct 384 ms 4884 KB Output is correct
11 Correct 1197 ms 24288 KB Output is correct
12 Correct 1426 ms 24288 KB Output is correct
13 Execution timed out 2021 ms 24288 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 4604 KB Output is correct
2 Correct 368 ms 4656 KB Output is correct
3 Correct 381 ms 4692 KB Output is correct
4 Correct 439 ms 4800 KB Output is correct
5 Correct 378 ms 4812 KB Output is correct
6 Correct 371 ms 4828 KB Output is correct
7 Correct 392 ms 4828 KB Output is correct
8 Correct 399 ms 4828 KB Output is correct
9 Correct 408 ms 4884 KB Output is correct
10 Correct 384 ms 4884 KB Output is correct
11 Correct 444 ms 24288 KB Output is correct
12 Correct 456 ms 24288 KB Output is correct
13 Correct 479 ms 24288 KB Output is correct
14 Correct 498 ms 24288 KB Output is correct
15 Correct 495 ms 24288 KB Output is correct
16 Correct 455 ms 24288 KB Output is correct
17 Correct 459 ms 24288 KB Output is correct
18 Correct 452 ms 24288 KB Output is correct
19 Correct 440 ms 24288 KB Output is correct
20 Correct 425 ms 24288 KB Output is correct
21 Correct 469 ms 24288 KB Output is correct
22 Correct 462 ms 24288 KB Output is correct
23 Correct 430 ms 24288 KB Output is correct
24 Correct 484 ms 24288 KB Output is correct
25 Correct 476 ms 24288 KB Output is correct
26 Correct 403 ms 24288 KB Output is correct
27 Correct 450 ms 24288 KB Output is correct
28 Correct 447 ms 24288 KB Output is correct
29 Correct 467 ms 24288 KB Output is correct
30 Correct 467 ms 24288 KB Output is correct
31 Correct 499 ms 24288 KB Output is correct
32 Correct 462 ms 24288 KB Output is correct
33 Correct 453 ms 24288 KB Output is correct
34 Correct 431 ms 24288 KB Output is correct
35 Correct 469 ms 24288 KB Output is correct
36 Correct 470 ms 24288 KB Output is correct
37 Correct 499 ms 24288 KB Output is correct
38 Correct 468 ms 24288 KB Output is correct
39 Correct 482 ms 24288 KB Output is correct
40 Correct 472 ms 24288 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 4604 KB Output is correct
2 Correct 368 ms 4656 KB Output is correct
3 Correct 381 ms 4692 KB Output is correct
4 Correct 439 ms 4800 KB Output is correct
5 Correct 378 ms 4812 KB Output is correct
6 Correct 371 ms 4828 KB Output is correct
7 Correct 392 ms 4828 KB Output is correct
8 Correct 399 ms 4828 KB Output is correct
9 Correct 408 ms 4884 KB Output is correct
10 Correct 384 ms 4884 KB Output is correct
11 Correct 1197 ms 24288 KB Output is correct
12 Correct 1426 ms 24288 KB Output is correct
13 Execution timed out 2021 ms 24288 KB Time limit exceeded
14 Halted 0 ms 0 KB -