oj.uz

Submission #125697

# Submission time Handle Problem Language Result Execution time Memory
125697 2019-07-06T08:57:23 Z 김세빈(#3068) Snake Escaping (JOI18_snake_escaping) C++14
0 / 100
 3 ms 376 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{
			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:45:20: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     else v += S[i] - '0' << i;
               ~~~~~^~~~~
snake_escaping.cpp:52: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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 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 Incorrect 3 ms 376 KB Output isn't correct
3 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 Incorrect 3 ms 376 KB Output isn't correct
3 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 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -