oj.uz

Submission #125699

# Submission time Handle Problem Language Result Execution time Memory
125699 2019-07-06T08:58:50 Z 김세빈(#3068) Snake Escaping (JOI18_snake_escaping) C++14
5 / 100
 2000 ms 11896 KB 
#include <bits/stdc++.h>

using namespace std;

char S[1101010];
int D1[1101010], D2[1101010];
int n, q;

int main()
{
	vector <int> X;
	int i, j, v, s, ans;
	
	scanf("%d%d%s", &n, &q, S);
	
	for(i=0; i<(1<<n); i++){
		D1[i] = D2[i] = S[i] - '0';
	}
	
	for(i=0; i<n; i++){
		for(j=0; j<(1<<n); j++){
			if(j & (1 << i)){
				D1[j] += D1[j - (1 << i)];
			}
		}
	}
	
	for(; q--; ){
		scanf("%s", S); reverse(S, S + n);
		
		for(i=0, s=0; i<n; i++){
			if(S[i] == '?') s ++;
		}
		
		if(s > 10){
			for(i=0; i<n; i++){
				if(S[i] == '1') X.push_back(i);
				else if(S[i] == '?') v += S[i] - '0' << i;
			}
		}
		else{
			X.clear(); ans = 0; v = 0;
			
			for(i=0; i<n; i++){
				if(S[i] == '?') X.push_back(i);
				else v += S[i] - '0' << i;
			}
			
			s = X.size();
			
			for(i=0; i<(1<<s); i++){
				ans += D2[v];
				for(j=0; (2<<j)<(i^i+1); j++){
					v -= 1 << X[j];
				}
				if(j < s) v += 1 << X[j];
			}
		}
		
		printf("%d\n", ans);
	}
	
	return 0;
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:38:36: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     else if(S[i] == '?') v += S[i] - '0' << i;
                               ~~~~~^~~~~
snake_escaping.cpp:46:20: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     else v += S[i] - '0' << i;
               ~~~~~^~~~~
snake_escaping.cpp:53:25: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     for(j=0; (2<<j)<(i^i+1); j++){
                        ~^~
snake_escaping.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%s", &n, &q, S);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", S); reverse(S, S + n);
   ~~~~~^~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 7 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 446 ms 9620 KB Output is correct
12 Correct 581 ms 9080 KB Output is correct
13 Correct 308 ms 8440 KB Output is correct
14 Correct 306 ms 8620 KB Output is correct
15 Correct 586 ms 9504 KB Output is correct
16 Correct 377 ms 8612 KB Output is correct
17 Correct 378 ms 8612 KB Output is correct
18 Execution timed out 2045 ms 7492 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 7 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 446 ms 9620 KB Output is correct
12 Correct 581 ms 9080 KB Output is correct
13 Correct 308 ms 8440 KB Output is correct
14 Correct 306 ms 8620 KB Output is correct
15 Correct 586 ms 9504 KB Output is correct
16 Correct 377 ms 8612 KB Output is correct
17 Correct 378 ms 8612 KB Output is correct
18 Execution timed out 2045 ms 7492 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 7 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 334 ms 11884 KB Output is correct
12 Incorrect 138 ms 11896 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 7 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 446 ms 9620 KB Output is correct
12 Correct 581 ms 9080 KB Output is correct
13 Correct 308 ms 8440 KB Output is correct
14 Correct 306 ms 8620 KB Output is correct
15 Correct 586 ms 9504 KB Output is correct
16 Correct 377 ms 8612 KB Output is correct
17 Correct 378 ms 8612 KB Output is correct
18 Execution timed out 2045 ms 7492 KB Time limit exceeded
19 Halted 0 ms 0 KB -