oj.uz

답안 #60727

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
60727 2018-07-24T15:21:05 Z gusfring Snake Escaping (JOI18_snake_escaping) C++14
5 / 100
 501 ms 66560 KB 
#include <stdio.h>
 
int L,Q;
char sc[1<<10+2]; int bc[1<<10];
int Z[1<<10],O[1<<10];
 
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<<10+2]; int bc[1<<10];
            ~~^~
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 376 KB Output is correct
3 Correct 3 ms 644 KB Output is correct
4 Correct 4 ms 644 KB Output is correct
5 Correct 4 ms 732 KB Output is correct
6 Correct 4 ms 732 KB Output is correct
7 Correct 4 ms 804 KB Output is correct
8 Correct 3 ms 816 KB Output is correct
9 Correct 3 ms 828 KB Output is correct
10 Correct 3 ms 828 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 644 KB Output is correct
4 Correct 4 ms 644 KB Output is correct
5 Correct 4 ms 732 KB Output is correct
6 Correct 4 ms 732 KB Output is correct
7 Correct 4 ms 804 KB Output is correct
8 Correct 3 ms 816 KB Output is correct
9 Correct 3 ms 828 KB Output is correct
10 Correct 3 ms 828 KB Output is correct
11 Correct 492 ms 15560 KB Output is correct
12 Correct 482 ms 25884 KB Output is correct
13 Correct 466 ms 36208 KB Output is correct
14 Correct 437 ms 46876 KB Output is correct
15 Correct 501 ms 58676 KB Output is correct
16 Runtime error 462 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.
17 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 644 KB Output is correct
4 Correct 4 ms 644 KB Output is correct
5 Correct 4 ms 732 KB Output is correct
6 Correct 4 ms 732 KB Output is correct
7 Correct 4 ms 804 KB Output is correct
8 Correct 3 ms 816 KB Output is correct
9 Correct 3 ms 828 KB Output is correct
10 Correct 3 ms 828 KB Output is correct
11 Correct 492 ms 15560 KB Output is correct
12 Correct 482 ms 25884 KB Output is correct
13 Correct 466 ms 36208 KB Output is correct
14 Correct 437 ms 46876 KB Output is correct
15 Correct 501 ms 58676 KB Output is correct
16 Runtime error 462 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.
17 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 376 KB Output is correct
3 Correct 3 ms 644 KB Output is correct
4 Correct 4 ms 644 KB Output is correct
5 Correct 4 ms 732 KB Output is correct
6 Correct 4 ms 732 KB Output is correct
7 Correct 4 ms 804 KB Output is correct
8 Correct 3 ms 816 KB Output is correct
9 Correct 3 ms 828 KB Output is correct
10 Correct 3 ms 828 KB Output is correct
11 Runtime error 4 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 376 KB Output is correct
3 Correct 3 ms 644 KB Output is correct
4 Correct 4 ms 644 KB Output is correct
5 Correct 4 ms 732 KB Output is correct
6 Correct 4 ms 732 KB Output is correct
7 Correct 4 ms 804 KB Output is correct
8 Correct 3 ms 816 KB Output is correct
9 Correct 3 ms 828 KB Output is correct
10 Correct 3 ms 828 KB Output is correct
11 Correct 492 ms 15560 KB Output is correct
12 Correct 482 ms 25884 KB Output is correct
13 Correct 466 ms 36208 KB Output is correct
14 Correct 437 ms 46876 KB Output is correct
15 Correct 501 ms 58676 KB Output is correct
16 Runtime error 462 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.
17 Halted 0 ms 0 KB -