oj.uz

Submission #256800

# Submission time Handle Problem Language Result Execution time Memory
256800 2020-08-03T08:29:22 Z 송준혁(#5037) Snake Escaping (JOI18_snake_escaping) C++17
5 / 100
 2000 ms 10300 KB 
#include <bits/stdc++.h>
#define pb push_back
#define lb lower_bound
#define fi first
#define se second
#define mup(a,x) a=min(a,x)
#define Mup(a,x) a=max(a,x)
#define INF 1234567890
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, Q;
int A[1050505], D1[1050505], D2[1050505];
char str[22];

int qm(int lv, int x){
	if (lv==N) return A[x];
	if (str[lv] == '?') return qm(lv+1, x*2+1)+qm(lv+1, x*2);
	return qm(lv+1, x*2+str[lv]-'0');
}

int inex0(int lv, int t, int x){
	if (lv==N) return (t&1)?-D1[x]:D1[x];
	if (str[lv] == '1') return inex0(lv+1, t, x*2+1)+inex0(lv+1, t+1, x*2);
	return inex0(lv+1, t, x*2+(x=='?'));
}

int inex1(int lv, int t, int x){
	if (lv==N) return (t&1)?-D2[x]:D2[x];
	if (str[lv] == '0') return inex1(lv+1, t, x*2+1)+inex1(lv+1, t+1, x*2);
	return inex1(lv+1, t, x*2+(x=='?'));
}

int main(){
	scanf("%d %d", &N, &Q);
	for (int i=0; i<(1<<N); i++) scanf("%1d", &A[i]);
	for (int i=0; i<(1<<N); i++){
		for (int j=i; j; j=i&(j-1)) D1[i] += A[j], D2[i] += A[(~j)&((1<<N)-1)];
		D1[i] += A[0], D2[i] += A[(1<<N)-1];
	}
	while (Q--){
		int x, y;
		scanf("%s", str);
		for (int i=0; i<N; i++){
			if (str[i] == '0') x++;
			if (str[i] == '1') y++;
		}
		if (x<=6) printf("%d\n", inex1(0, 0, 0));
		else if (y<=6) printf("%d\n", inex0(0, 0, 0));
		else printf("%d\n", qm(0, 0));
	}
	return 0;
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~
snake_escaping.cpp:37:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=0; i<(1<<N); i++) scanf("%1d", &A[i]);
                               ~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", str);
   ~~~~~^~~~~~~~~~~
snake_escaping.cpp:47:24: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if (str[i] == '1') y++;
                       ~^~
snake_escaping.cpp:46:24: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if (str[i] == '0') x++;
                       ~^~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 617 ms 6904 KB Output is correct
12 Correct 803 ms 6392 KB Output is correct
13 Correct 440 ms 5880 KB Output is correct
14 Correct 426 ms 5756 KB Output is correct
15 Correct 849 ms 6880 KB Output is correct
16 Correct 532 ms 6008 KB Output is correct
17 Correct 524 ms 6108 KB Output is correct
18 Execution timed out 2089 ms 3684 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 617 ms 6904 KB Output is correct
12 Correct 803 ms 6392 KB Output is correct
13 Correct 440 ms 5880 KB Output is correct
14 Correct 426 ms 5756 KB Output is correct
15 Correct 849 ms 6880 KB Output is correct
16 Correct 532 ms 6008 KB Output is correct
17 Correct 524 ms 6108 KB Output is correct
18 Execution timed out 2089 ms 3684 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

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

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 617 ms 6904 KB Output is correct
12 Correct 803 ms 6392 KB Output is correct
13 Correct 440 ms 5880 KB Output is correct
14 Correct 426 ms 5756 KB Output is correct
15 Correct 849 ms 6880 KB Output is correct
16 Correct 532 ms 6008 KB Output is correct
17 Correct 524 ms 6108 KB Output is correct
18 Execution timed out 2089 ms 3684 KB Time limit exceeded
19 Halted 0 ms 0 KB -