oj.uz

Submission #60729

# Submission time Handle Problem Language Result Execution time Memory
60729 2018-07-24T15:36:38 Z gusfring Snake Escaping (JOI18_snake_escaping) C++14
12 / 100
 749 ms 66560 KB 
#include <stdio.h>
 
int L,Q;
char sc[1<<14+2]; int bc[1<<14];
int Z[1<<14],O[1<<14];
 
void go(int l, int r)
{
	if (l+1 == r) return;
 
	int m = (l + r) / 2;
	go(l,m);
	go(m,r);
	for (int i=l;i<m;i++){
		Z[i-l+m] += Z[i];
		O[i] += O[i-l+m];
	}
}
 
int main()
{
	scanf ("%d %d",&L,&Q);
	scanf ("%s",sc);
 
	for (int i=0;i<(1<<L);i++){
		if (i) bc[i] = bc[i-(i&(-i))] + 1;
		Z[i] = O[i] = sc[i] - '0';
	}
	go(0,(1<<L));
 
	while (Q--){
		char q[22]; scanf ("%s",q);
		int z = 0, o = 0, f = 0;
		for (int i=0;i<L;i++){
			if (q[i] == '0') z |= 1 << (L - i - 1);
			if (q[i] == '1') o |= 1 << (L - i - 1);
			if (q[i] == '?') f |= 1 << (L - i - 1);
		}
		int ans = 0;
		if (bc[f] <= 7){
			for (int x=f;;x=(x-1)&f){
				ans += sc[x|o] - '0';
				if (!x) break;
			}
		}
		else if (bc[o] <= 7){
			for (int x=o;;x=(x-1)&o){
				int b = f + x;
				if (bc[o] % 2 != bc[x] % 2) ans -= Z[b];
				else ans += Z[b];
				if (!x) break;
			}
		}
		else{
			for (int x=z;;x=(x-1)&z){
				int b = o + z - x;
				if (bc[z] % 2 != bc[x] % 2) ans -= O[b];
				else ans += O[b];
				if (!x) break;
			}
		}
		printf ("%d\n",ans);
	}
	return 0;
}

Compilation message

snake_escaping.cpp:4:14: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
 char sc[1<<14+2]; int bc[1<<14];
            ~~^~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d",&L,&Q);
  ~~~~~~^~~~~~~~~~~~~~~
snake_escaping.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%s",sc);
  ~~~~~~^~~~~~~~~
snake_escaping.cpp:32:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char q[22]; scanf ("%s",q);
               ~~~~~~^~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 3 ms 556 KB Output is correct
4 Correct 4 ms 556 KB Output is correct
5 Correct 4 ms 568 KB Output is correct
6 Correct 3 ms 568 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 3 ms 652 KB Output is correct
9 Correct 3 ms 664 KB Output is correct
10 Correct 3 ms 676 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 3 ms 556 KB Output is correct
4 Correct 4 ms 556 KB Output is correct
5 Correct 4 ms 568 KB Output is correct
6 Correct 3 ms 568 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 3 ms 652 KB Output is correct
9 Correct 3 ms 664 KB Output is correct
10 Correct 3 ms 676 KB Output is correct
11 Correct 371 ms 6744 KB Output is correct
12 Correct 489 ms 6744 KB Output is correct
13 Correct 446 ms 6744 KB Output is correct
14 Correct 415 ms 6744 KB Output is correct
15 Correct 435 ms 6744 KB Output is correct
16 Correct 461 ms 6744 KB Output is correct
17 Correct 402 ms 16696 KB Output is correct
18 Correct 382 ms 29372 KB Output is correct
19 Correct 324 ms 37068 KB Output is correct
20 Correct 407 ms 49544 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 3 ms 556 KB Output is correct
4 Correct 4 ms 556 KB Output is correct
5 Correct 4 ms 568 KB Output is correct
6 Correct 3 ms 568 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 3 ms 652 KB Output is correct
9 Correct 3 ms 664 KB Output is correct
10 Correct 3 ms 676 KB Output is correct
11 Correct 371 ms 6744 KB Output is correct
12 Correct 489 ms 6744 KB Output is correct
13 Correct 446 ms 6744 KB Output is correct
14 Correct 415 ms 6744 KB Output is correct
15 Correct 435 ms 6744 KB Output is correct
16 Correct 461 ms 6744 KB Output is correct
17 Correct 402 ms 16696 KB Output is correct
18 Correct 382 ms 29372 KB Output is correct
19 Correct 324 ms 37068 KB Output is correct
20 Correct 407 ms 49544 KB Output is correct
21 Correct 749 ms 63648 KB Output is correct
22 Runtime error 659 ms 66560 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.
23 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 3 ms 556 KB Output is correct
4 Correct 4 ms 556 KB Output is correct
5 Correct 4 ms 568 KB Output is correct
6 Correct 3 ms 568 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 3 ms 652 KB Output is correct
9 Correct 3 ms 664 KB Output is correct
10 Correct 3 ms 676 KB Output is correct
11 Runtime error 5 ms 66560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 3 ms 556 KB Output is correct
4 Correct 4 ms 556 KB Output is correct
5 Correct 4 ms 568 KB Output is correct
6 Correct 3 ms 568 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 3 ms 652 KB Output is correct
9 Correct 3 ms 664 KB Output is correct
10 Correct 3 ms 676 KB Output is correct
11 Correct 371 ms 6744 KB Output is correct
12 Correct 489 ms 6744 KB Output is correct
13 Correct 446 ms 6744 KB Output is correct
14 Correct 415 ms 6744 KB Output is correct
15 Correct 435 ms 6744 KB Output is correct
16 Correct 461 ms 6744 KB Output is correct
17 Correct 402 ms 16696 KB Output is correct
18 Correct 382 ms 29372 KB Output is correct
19 Correct 324 ms 37068 KB Output is correct
20 Correct 407 ms 49544 KB Output is correct
21 Correct 749 ms 63648 KB Output is correct
22 Runtime error 659 ms 66560 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.
23 Halted 0 ms 0 KB -