답안 #60729 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60729	2018-07-24T15:36:38 Z	gusfring	Snake Escaping (JOI18_snake_escaping)	C++14	12 / 100	749 ms	66560 KB

snake_escaping

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #60729

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 10.0

Subtask #4 0 / 53.0

Subtask #5 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
0 / 10.0

Subtask #4
0 / 53.0

Subtask #5
0 / 25.0