oj.uz

Submission #208826

# Submission time Handle Problem Language Result Execution time Memory
208826 2020-03-12T09:03:26 Z Siberian Snake Escaping (JOI18_snake_escaping) C++14
12 / 100
 2000 ms 5864 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define all(x) x.begin(), x.end()

template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 & y) {if (x > y) x = y;}
template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 & y) {if (x < y) x = y;}

int n, q;
string s;

void read() {
	cin >> n >> q;
	cin >> s;
}

pair<int, int> get_mask() {
	string s;
	cin >> s;
	int mask = 0;
	int must = 0;
	for (int i = 0; i < n; i++) {
		mask *= 2;
		if (s[i] != '0') mask++;
		must *= 2;
		if (s[i] == '1') must++;
	}
	return {mask, must};
}

void build() {

}

bool check_submask(int mask, int submask) {
	return (mask & submask) == submask;
}

void solve() {
	auto x = get_mask();
	int mask = x.first, must = x.second;
	int ans = 0;
	//cout << "mask = " << mask << endl;
	for (int i = mask; i >= 0; i = (i - 1) & mask) {
		if (check_submask(i, must)) ans += s[i] - '0';
		if (i == 0) break;
	}
	cout << ans << "\n";
}

void run() {
	build();
	while (q--) {
		solve();
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	read();
	run();
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Correct 6 ms 380 KB Output is correct
8 Correct 6 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 1252 ms 4748 KB Output is correct
12 Correct 341 ms 4460 KB Output is correct
13 Correct 321 ms 3704 KB Output is correct
14 Correct 378 ms 3864 KB Output is correct
15 Correct 673 ms 4856 KB Output is correct
16 Correct 438 ms 3960 KB Output is correct
17 Correct 467 ms 3960 KB Output is correct
18 Correct 1564 ms 5864 KB Output is correct
19 Correct 279 ms 2936 KB Output is correct
20 Correct 1264 ms 4592 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Correct 6 ms 380 KB Output is correct
8 Correct 6 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 1252 ms 4748 KB Output is correct
12 Correct 341 ms 4460 KB Output is correct
13 Correct 321 ms 3704 KB Output is correct
14 Correct 378 ms 3864 KB Output is correct
15 Correct 673 ms 4856 KB Output is correct
16 Correct 438 ms 3960 KB Output is correct
17 Correct 467 ms 3960 KB Output is correct
18 Correct 1564 ms 5864 KB Output is correct
19 Correct 279 ms 2936 KB Output is correct
20 Correct 1264 ms 4592 KB Output is correct
21 Execution timed out 2067 ms 3692 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

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

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Correct 6 ms 380 KB Output is correct
8 Correct 6 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 1252 ms 4748 KB Output is correct
12 Correct 341 ms 4460 KB Output is correct
13 Correct 321 ms 3704 KB Output is correct
14 Correct 378 ms 3864 KB Output is correct
15 Correct 673 ms 4856 KB Output is correct
16 Correct 438 ms 3960 KB Output is correct
17 Correct 467 ms 3960 KB Output is correct
18 Correct 1564 ms 5864 KB Output is correct
19 Correct 279 ms 2936 KB Output is correct
20 Correct 1264 ms 4592 KB Output is correct
21 Execution timed out 2067 ms 3692 KB Time limit exceeded
22 Halted 0 ms 0 KB -