oj.uz

Submission #64544

# Submission time Handle Problem Language Result Execution time Memory
64544 2018-08-04T20:42:17 Z keko37 Snake Escaping (JOI18_snake_escaping) C++14
5 / 100
 2000 ms 66408 KB 
#include<iostream>

using namespace std;

const int MAXN = 21;

int n, q;
char l[MAXN];
int val[1<<MAXN], sum0[1<<MAXN], sum1[1<<MAXN];

void precompute () {
	for (int i=0; i<(1<<n); i++) {
		sum0[i] = val[i];
		sum1[i] = val[i ^ ((1<<n) - 1)];
	}
	for (int i=0; i<n; i++) {
		for (int j=0; j<(1<<n); j++) {
			if (j & (1<<i)) sum0[j] += sum0[j ^ (1<<i)];
			if (j & (1<<i)) sum1[j] += sum1[j ^ (1<<i)];
		}
	}
}

void ispis (int x) {
	for (int i=n-1; i>=0; i--) {
		cout << (bool) (x & (1<<i));
	}
	cout << endl;
}

int main () {
	cin >> n >> q;
	for (int i=0; i<(1<<n); i++) {
		char c;
		cin >> c;
		val[i] = c - '0';
	}
	precompute();
	for (int tc=0; tc<q; tc++) {
		int a = 0, b = 0, c = 0;
		for (int i=0; i<n; i++) {
			cin >> l[i];
			if (l[i] == '?') {
				a ^= (1<<(n-1-i));
			} else if (l[i] == '0') {
				b ^= (1<<(n-1-i));
			} else {
				c ^= (1<<(n-1-i));
			}
		}
		int sol = 0, mask = 0;
		if (__builtin_popcount(a) <= n/3) {
			do {
				sol += val[mask | c];
			} while (mask = (mask-a) & a);
		} else if (__builtin_popcount(b) <= n/3) {
			do {
				if (__builtin_popcount(mask | a) & 1) {
					sol -= sum1[mask | a];
				} else {
					sol += sum1[mask | a];
				}
			} while (mask = (mask-b) & b);
			if (sol < 0) sol = -sol;
		} else {
			do {
				if (__builtin_popcount(mask | a) & 1) {
					sol -= sum0[mask | a];
				} else {
					sol += sum0[mask | a];
				}
			} while (mask = (mask-c) & c);
			if (sol < 0) sol = -sol;
		}
		printf("%d\n", sol);
	}
	return 0;
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:55:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    } while (mask = (mask-a) & a);
             ~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:63:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    } while (mask = (mask-b) & b);
             ~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:72:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    } while (mask = (mask-c) & c);
             ~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 452 KB Output is correct
3 Correct 7 ms 648 KB Output is correct
4 Correct 8 ms 648 KB Output is correct
5 Correct 5 ms 648 KB Output is correct
6 Correct 5 ms 648 KB Output is correct
7 Correct 6 ms 748 KB Output is correct
8 Correct 5 ms 748 KB Output is correct
9 Correct 6 ms 748 KB Output is correct
10 Correct 6 ms 748 KB Output is correct
11 Execution timed out 2019 ms 11072 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 452 KB Output is correct
3 Correct 7 ms 648 KB Output is correct
4 Correct 8 ms 648 KB Output is correct
5 Correct 5 ms 648 KB Output is correct
6 Correct 5 ms 648 KB Output is correct
7 Correct 6 ms 748 KB Output is correct
8 Correct 5 ms 748 KB Output is correct
9 Correct 6 ms 748 KB Output is correct
10 Correct 6 ms 748 KB Output is correct
11 Execution timed out 2019 ms 11072 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 452 KB Output is correct
3 Correct 7 ms 648 KB Output is correct
4 Correct 8 ms 648 KB Output is correct
5 Correct 5 ms 648 KB Output is correct
6 Correct 5 ms 648 KB Output is correct
7 Correct 6 ms 748 KB Output is correct
8 Correct 5 ms 748 KB Output is correct
9 Correct 6 ms 748 KB Output is correct
10 Correct 6 ms 748 KB Output is correct
11 Correct 378 ms 23024 KB Output is correct
12 Correct 321 ms 25224 KB Output is correct
13 Correct 293 ms 27136 KB Output is correct
14 Correct 427 ms 29120 KB Output is correct
15 Correct 330 ms 31396 KB Output is correct
16 Correct 364 ms 33208 KB Output is correct
17 Correct 344 ms 35376 KB Output is correct
18 Correct 343 ms 37560 KB Output is correct
19 Correct 316 ms 39464 KB Output is correct
20 Correct 284 ms 41808 KB Output is correct
21 Correct 334 ms 43664 KB Output is correct
22 Correct 380 ms 45684 KB Output is correct
23 Correct 302 ms 47624 KB Output is correct
24 Correct 376 ms 49952 KB Output is correct
25 Correct 388 ms 51808 KB Output is correct
26 Correct 293 ms 53936 KB Output is correct
27 Correct 275 ms 56100 KB Output is correct
28 Correct 314 ms 58000 KB Output is correct
29 Correct 345 ms 60108 KB Output is correct
30 Correct 415 ms 62160 KB Output is correct
31 Correct 297 ms 64100 KB Output is correct
32 Runtime error 386 ms 66408 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
33 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 452 KB Output is correct
3 Correct 7 ms 648 KB Output is correct
4 Correct 8 ms 648 KB Output is correct
5 Correct 5 ms 648 KB Output is correct
6 Correct 5 ms 648 KB Output is correct
7 Correct 6 ms 748 KB Output is correct
8 Correct 5 ms 748 KB Output is correct
9 Correct 6 ms 748 KB Output is correct
10 Correct 6 ms 748 KB Output is correct
11 Execution timed out 2019 ms 11072 KB Time limit exceeded
12 Halted 0 ms 0 KB -