Submission #101819

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
101819	2019-03-20T12:02:53 Z	KCSC	Snake Escaping (JOI18_snake_escaping)	C++14	5 / 100	2000 ms	14048 KB

snake_escaping

#include <bits/stdc++.h>
using namespace std;

const int DIM = 20;

char str[1 << DIM | 3], aux[DIM + 2];
int udp[1 << DIM], ddp[1 << DIM], cbit[1 << DIM];

int main(void) {
#ifdef HOME
	freopen("snake.in", "r", stdin);
	freopen("snake.out", "w", stdout);
#endif
	int n, q; cin >> n >> q >> str;
	for (int msk = 0; msk < (1 << n); ++msk) {
		cbit[msk] = cbit[msk >> 1] + (msk & 1);
		udp[msk] = ddp[msk] = str[msk] - '0'; }
	for (int b = 0; b < n; ++b) {
		for (int msk = 0; msk < (1 << n); ++msk) {
			if (msk & (1 << b)) {
				udp[msk ^ (1 << b)] += udp[msk]; }
			else {
				ddp[msk ^ (1 << b)] += ddp[msk]; } } }
	while (q--) {
		int msk0 = 0, msk1 = 0, mskq = 0; 
		cin >> aux; reverse(aux, aux + n);
		for (int i = 0; i < n; ++i) {
			if (aux[i] == '0') { msk0 ^= (1 << i); } 
			if (aux[i] == '1') { msk1 ^= (1 << i); }
			if (aux[i] == '?') { mskq ^= (1 << i); } }
		int ans = 0;
		if (cbit[mskq] <= -1) {
			for (int axm = mskq, nr = (1 << cbit[mskq]); nr; (--axm) &= mskq, --nr) {
				ans += str[axm ^ msk1] - '0'; } }
		else if (cbit[msk0] <= 7) {
			for (int axm = msk0, nr = (1 << cbit[msk0]); nr; (--axm) &= msk0, --nr) {
				ans += udp[msk1 ^ axm] * ((cbit[axm] & 1) ? -1 : 1); } }
		else if (cbit[msk1] <= 7) {
			for (int axm = msk1, nr = (1 << cbit[msk1]); nr; (--axm) &= msk1, --nr) {
				ans += ddp[mskq ^ msk1 ^ axm] * ((cbit[axm] & 1) ? -1 : 1); } }
		cout << ans << "\n"; }		   
	return 0; }

Subtask #1

5.0 / 5.0

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

Subtask #2

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	4 ms	384 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	4 ms	384 KB	Output is correct
9	Correct	6 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Execution timed out	2029 ms	4508 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	4 ms	384 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	4 ms	384 KB	Output is correct
9	Correct	6 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Execution timed out	2029 ms	4508 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #4

0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	4 ms	384 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	4 ms	384 KB	Output is correct
9	Correct	6 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	186 ms	13976 KB	Output is correct
12	Correct	213 ms	14048 KB	Output is correct
13	Incorrect	235 ms	13972 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #5

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	4 ms	384 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	4 ms	384 KB	Output is correct
9	Correct	6 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Execution timed out	2029 ms	4508 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-