oj.uz

Submission #42370

# Submission time Handle Problem Language Result Execution time Memory
42370 2018-02-26T14:50:06 Z RezwanArefin01 Snake Escaping (JOI18_snake_escaping) C++14
5 / 100
 2000 ms 36952 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

ll dp[1 << 20], ans; 
string b, s; int l, q;

void recurr1(int i, int num, int tot) {
	if(i == s.size()) {

		if(tot & 1) ans -= dp[num];
		else ans += dp[num];
		return; 
	}
	if(s[i] == '0') {
		recurr1(i + 1, num << 1, tot); 
	} else if(s[i] == '?') {
		recurr1(i + 1, num << 1 | 1, tot);
	} else {
		recurr1(i + 1, num << 1 | 1, tot); 
		recurr1(i + 1, num << 1, tot + 1);
	}
}

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> l >> q >> b;
	for(int i = 0; i < (1 << l); i++) {
		dp[i] = b[i] - '0';
	}
	for(int i = 0; i < l; i++) {
		for(int j = 0; j < (1 << l); j++) {
			if(j >> i & 1) 
				dp[j] += dp[j ^ (1 << i)];
		}
	}
	while(q--) {
		cin >> s; 
		int n0 = 0, n1 = 0, nw0t = 0; 
		for(char c : s) {
			n0 += c == '0';
			n1 += c == '1';
			nw0t += c == '?';
		}

		if(n1 == 0) {
			int num = 0;
			for(char c : s) num = (num << 1) + (c == '?');
			cout << dp[num] << endl;
		} else if(nw0t == 0) {
			int num = 0;
			for(char c : s) num = (num << 1) + (c == '1');
			cout << b[num] << endl;
		} else {
			//if(n1 <= n0 && n1 <= nw0t) {
				ans = 0;
				recurr1(0, 0, 0);
			//} 
			cout << ans << endl;
		}
	}
}

Compilation message

snake_escaping.cpp: In function 'void recurr1(int, int, int)':
snake_escaping.cpp:11:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(i == s.size()) {
       ^

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 3 ms 480 KB Output is correct
3 Correct 3 ms 480 KB Output is correct
4 Correct 4 ms 544 KB Output is correct
5 Correct 3 ms 544 KB Output is correct
6 Correct 4 ms 544 KB Output is correct
7 Correct 4 ms 584 KB Output is correct
8 Correct 3 ms 584 KB Output is correct
9 Correct 3 ms 584 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Execution timed out 2017 ms 6616 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 3 ms 480 KB Output is correct
3 Correct 3 ms 480 KB Output is correct
4 Correct 4 ms 544 KB Output is correct
5 Correct 3 ms 544 KB Output is correct
6 Correct 4 ms 544 KB Output is correct
7 Correct 4 ms 584 KB Output is correct
8 Correct 3 ms 584 KB Output is correct
9 Correct 3 ms 584 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Execution timed out 2017 ms 6616 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 3 ms 480 KB Output is correct
3 Correct 3 ms 480 KB Output is correct
4 Correct 4 ms 544 KB Output is correct
5 Correct 3 ms 544 KB Output is correct
6 Correct 4 ms 544 KB Output is correct
7 Correct 4 ms 584 KB Output is correct
8 Correct 3 ms 584 KB Output is correct
9 Correct 3 ms 584 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Correct 839 ms 12512 KB Output is correct
12 Correct 135 ms 14488 KB Output is correct
13 Correct 253 ms 16648 KB Output is correct
14 Correct 301 ms 18864 KB Output is correct
15 Correct 180 ms 20772 KB Output is correct
16 Correct 553 ms 22832 KB Output is correct
17 Correct 519 ms 24928 KB Output is correct
18 Correct 117 ms 27064 KB Output is correct
19 Correct 123 ms 28800 KB Output is correct
20 Correct 1829 ms 31180 KB Output is correct
21 Correct 227 ms 33104 KB Output is correct
22 Correct 383 ms 35220 KB Output is correct
23 Execution timed out 2039 ms 36952 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 3 ms 480 KB Output is correct
3 Correct 3 ms 480 KB Output is correct
4 Correct 4 ms 544 KB Output is correct
5 Correct 3 ms 544 KB Output is correct
6 Correct 4 ms 544 KB Output is correct
7 Correct 4 ms 584 KB Output is correct
8 Correct 3 ms 584 KB Output is correct
9 Correct 3 ms 584 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Execution timed out 2017 ms 6616 KB Time limit exceeded
12 Halted 0 ms 0 KB -