oj.uz

Submission #943707

# Submission time Handle Problem Language Result Execution time Memory
943707 2024-03-11T18:25:36 Z guechotjrhh Snake Escaping (JOI18_snake_escaping) C++14
12 / 100
 2000 ms 20316 KB 
#include<iostream>
#include<string>
using namespace std;

#include<map>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
#define all(x) x.begin(),x.end()
string str;
int n,p;
vector<int> zer, on;//sum of those i contains, sum of those contains me i
void init(int N, int Q, string S) {
	n = N; p = 1 << n;
	str = S;
	zer.resize(p); on.resize(p);
	for (int i = 0; i < p; i++) zer[i] = on[i] = S[i] - '0';
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < p; j++) {
			if (j & (1 << i)) zer[j] += zer[j - (1 << i)];
			else on[j] += on[j + (1 << i)];
		}
	}
	//for (int i = 0; i < p; i++) cout << i << ' ' << zer[i] << endl;
	//for (int i = 0; i < p; i++) cout << i << ' ' << on[i] << endl;
}
int ab(int x) { return x > 0 ? x : -x; }
int query(string A) {
	vector<int> ze, o, q;
	for (int i = 0; i < n; i++) {
		if (A[i] == '0') ze.push_back(n-1-i);
		else if (A[i] == '1') o.push_back(n-1-i);
		else q.push_back(n-1-i);
	}
	if (ze.size() > o.size()) {
		int c = 0;
		for (int i : q) c += 1 << i;
		int res = 0;
		for (int i = 0; i < (1 << o.size()); i++) {
			int w = c, x=0;
			for (int j = 0; j < o.size(); j++) {
				if (i & (1 << j)) {
					w += 1 << o[j];
					x++;
				}
			}
			if (x & 1) res += zer[w];
			else res -= zer[w];
		}
		return ab(res);
	}
	else {
		int c = 0;
		for (int i : o) c += 1 << i;
		int res = 0;
		for (int i = 0; i < (1 << ze.size()); i++) {
			int w = c, x = 0;
			for (int j = 0; j < ze.size(); j++) {
				if (i & (1 << j)) {
					w += 1 << ze[j];
					x++;
				}
			}
			if (x & 1) res += on[w];
			else res -= on[w];
		}
		return ab(res);
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, Q; cin >> N >> Q;
	string S; cin >> S;
	init(N, Q, move(S));
	
	for (int i = 0; i < Q; i++) {
		string A;
		cin >> A;
		cout << query(move(A)) << endl;
	}
}

Compilation message

snake_escaping.cpp: In function 'int query(std::string)':
snake_escaping.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    for (int j = 0; j < o.size(); j++) {
      |                    ~~^~~~~~~~~~
snake_escaping.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    for (int j = 0; j < ze.size(); j++) {
      |                    ~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1473 ms 13308 KB Output is correct
12 Correct 1450 ms 13392 KB Output is correct
13 Correct 1555 ms 12736 KB Output is correct
14 Correct 1576 ms 12448 KB Output is correct
15 Correct 1517 ms 13608 KB Output is correct
16 Correct 1554 ms 12808 KB Output is correct
17 Correct 1554 ms 13044 KB Output is correct
18 Correct 1421 ms 14784 KB Output is correct
19 Correct 1736 ms 12012 KB Output is correct
20 Correct 1444 ms 13404 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1473 ms 13308 KB Output is correct
12 Correct 1450 ms 13392 KB Output is correct
13 Correct 1555 ms 12736 KB Output is correct
14 Correct 1576 ms 12448 KB Output is correct
15 Correct 1517 ms 13608 KB Output is correct
16 Correct 1554 ms 12808 KB Output is correct
17 Correct 1554 ms 13044 KB Output is correct
18 Correct 1421 ms 14784 KB Output is correct
19 Correct 1736 ms 12012 KB Output is correct
20 Correct 1444 ms 13404 KB Output is correct
21 Correct 1499 ms 18056 KB Output is correct
22 Correct 1508 ms 18204 KB Output is correct
23 Correct 1696 ms 17600 KB Output is correct
24 Correct 1697 ms 17112 KB Output is correct
25 Correct 1519 ms 19288 KB Output is correct
26 Correct 1675 ms 17848 KB Output is correct
27 Correct 1702 ms 17748 KB Output is correct
28 Correct 1375 ms 20316 KB Output is correct
29 Execution timed out 2048 ms 15964 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 108 ms 12104 KB Output is correct
12 Correct 104 ms 12032 KB Output is correct
13 Correct 150 ms 12032 KB Output is correct
14 Correct 136 ms 12020 KB Output is correct
15 Correct 105 ms 12028 KB Output is correct
16 Correct 160 ms 12028 KB Output is correct
17 Correct 155 ms 12028 KB Output is correct
18 Correct 99 ms 12164 KB Output is correct
19 Execution timed out 2057 ms 12144 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1473 ms 13308 KB Output is correct
12 Correct 1450 ms 13392 KB Output is correct
13 Correct 1555 ms 12736 KB Output is correct
14 Correct 1576 ms 12448 KB Output is correct
15 Correct 1517 ms 13608 KB Output is correct
16 Correct 1554 ms 12808 KB Output is correct
17 Correct 1554 ms 13044 KB Output is correct
18 Correct 1421 ms 14784 KB Output is correct
19 Correct 1736 ms 12012 KB Output is correct
20 Correct 1444 ms 13404 KB Output is correct
21 Correct 1499 ms 18056 KB Output is correct
22 Correct 1508 ms 18204 KB Output is correct
23 Correct 1696 ms 17600 KB Output is correct
24 Correct 1697 ms 17112 KB Output is correct
25 Correct 1519 ms 19288 KB Output is correct
26 Correct 1675 ms 17848 KB Output is correct
27 Correct 1702 ms 17748 KB Output is correct
28 Correct 1375 ms 20316 KB Output is correct
29 Execution timed out 2048 ms 15964 KB Time limit exceeded
30 Halted 0 ms 0 KB -