oj.uz

Submission #564019

# Submission time Handle Problem Language Result Execution time Memory
564019 2022-05-18T12:38:43 Z SeDunion Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 684 ms 20108 KB 
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("bmi,abm,fma,avx,avx2,popcnt,lzcnt")
#include <iostream>
#include <cassert>
#include <algorithm>
#include <string>
#include <bitset> 
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#ifndef LOCAL
	#include <bits/stdc++.h>
	#define cerr if(false)cerr
#endif
 
using namespace std;
using ll = long long;

const int N = 1e6 + 66;

int up[N];
int dw[N];
vector<int>pos;
string vals, qs;
int L;



int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int q;
	cin >> L >> q;
	cin >> vals;
	for (int i = 0 ; i < (1 << L) ; ++ i) {
		up[i] = dw[i] = vals[i] - '0';
	}
	for (int i = 0 ; i < L ; ++ i) {
		for (int m = 0 ; m < (1 << L) ; ++ m) {
			if (!(m >> i & 1)) {
				dw[m | (1 << i)] += dw[m];
			}
		}
	}
	for (int i = 0 ; i < L ; ++ i) {
		for (int m = (1 << L) - 1 ; m >= 0 ; -- m) {
			if (m >> i & 1) {
				up[m ^ (1 << i)] += up[m];
			}
		}
	}
	while (q--) {
		int ans = 0;
		cin >> qs;
		reverse(qs.begin(), qs.end());
		int a = count(qs.begin(), qs.end(), '0');
		int c = count(qs.begin(), qs.end(), '?');
		if (c <= 6) {
			pos.clear();
			for (int i = 0 ; i < L ; ++ i) {
				if (qs[i] == '?') {
					pos.emplace_back(i);
				}
			}
			int n = pos.size();
			int base = 0;
			for (int i = 0 ; i < L ; ++ i) {
				if (qs[i] == '1') {
					base |= 1 << i;
				}
			}
			for (int m = 0 ; m < (1 << n) ; ++ m) {
				int mask = base;
				for (int i = 0 ; i < n ; ++ i) {
					if (m >> i & 1) mask |= 1 << pos[i];
				}
				ans += vals[mask] - '0';
			}
		} else if (a <= 6) {
			pos.clear();
			for (int i = 0 ; i < L ; ++ i) {
				if (qs[i] == '0') {
					pos.emplace_back(i);
				}
			}
			int n = pos.size();
			int base = 0;
			for (int i = 0 ; i < L ; ++ i) {
				if (qs[i] == '1') {
					base |= 1 << i;
				}
			}
			for (int m = 0 ; m < (1 << n) ; ++ m) {
				int mask = base;
				for (int i = 0 ; i < n ; ++ i) {
					if (m >> i & 1) mask |= 1 << pos[i];
				}
				int par = __builtin_popcount(m) & 1;
				int cur = up[mask] * (par ? -1 : 1);
				ans += cur;
			}
		} else {
			pos.clear();
			for (int i = 0 ; i < L ; ++ i) {
				if (qs[i] == '1') {
					pos.emplace_back(i);
				}
			}
			int n = pos.size();
			int base = 0;
			for (int i = 0 ; i < L ; ++ i) {
				if (qs[i] == '?') {
					base |= 1 << i;
				}
			}
			for (int m = 0 ; m < (1 << n) ; ++ m) {
				int mask = 0;
				for (int i = 0 ; i < n ; ++ i) {
					if (m >> i & 1) mask |= 1 << pos[i];
				}
				int par = __builtin_popcount(((1 << n) - 1) ^ m) & 1;
				int cur = dw[mask] * (par ? -1 : 1);
				ans += cur;
			}
		}
		cout << ans << "\n";
	}
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 400 ms 4428 KB Output is correct
12 Correct 409 ms 3920 KB Output is correct
13 Correct 292 ms 3192 KB Output is correct
14 Correct 264 ms 3320 KB Output is correct
15 Correct 633 ms 7344 KB Output is correct
16 Correct 369 ms 14284 KB Output is correct
17 Correct 365 ms 14196 KB Output is correct
18 Correct 188 ms 16072 KB Output is correct
19 Correct 205 ms 13036 KB Output is correct
20 Correct 437 ms 14760 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 400 ms 4428 KB Output is correct
12 Correct 409 ms 3920 KB Output is correct
13 Correct 292 ms 3192 KB Output is correct
14 Correct 264 ms 3320 KB Output is correct
15 Correct 633 ms 7344 KB Output is correct
16 Correct 369 ms 14284 KB Output is correct
17 Correct 365 ms 14196 KB Output is correct
18 Correct 188 ms 16072 KB Output is correct
19 Correct 205 ms 13036 KB Output is correct
20 Correct 437 ms 14760 KB Output is correct
21 Correct 240 ms 18100 KB Output is correct
22 Correct 586 ms 18220 KB Output is correct
23 Correct 400 ms 17212 KB Output is correct
24 Correct 363 ms 17240 KB Output is correct
25 Correct 290 ms 19064 KB Output is correct
26 Correct 504 ms 17532 KB Output is correct
27 Correct 464 ms 17568 KB Output is correct
28 Correct 210 ms 20108 KB Output is correct
29 Correct 245 ms 16076 KB Output is correct
30 Correct 434 ms 18240 KB Output is correct
31 Correct 684 ms 18124 KB Output is correct
32 Correct 443 ms 18096 KB Output is correct
33 Correct 314 ms 17020 KB Output is correct
34 Correct 377 ms 17072 KB Output is correct
35 Correct 471 ms 17576 KB Output is correct
36 Correct 199 ms 16056 KB Output is correct
37 Correct 654 ms 18140 KB Output is correct
38 Correct 252 ms 16268 KB Output is correct
39 Correct 412 ms 17212 KB Output is correct
40 Correct 363 ms 17064 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Runtime error 16 ms 18680 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 400 ms 4428 KB Output is correct
12 Correct 409 ms 3920 KB Output is correct
13 Correct 292 ms 3192 KB Output is correct
14 Correct 264 ms 3320 KB Output is correct
15 Correct 633 ms 7344 KB Output is correct
16 Correct 369 ms 14284 KB Output is correct
17 Correct 365 ms 14196 KB Output is correct
18 Correct 188 ms 16072 KB Output is correct
19 Correct 205 ms 13036 KB Output is correct
20 Correct 437 ms 14760 KB Output is correct
21 Correct 240 ms 18100 KB Output is correct
22 Correct 586 ms 18220 KB Output is correct
23 Correct 400 ms 17212 KB Output is correct
24 Correct 363 ms 17240 KB Output is correct
25 Correct 290 ms 19064 KB Output is correct
26 Correct 504 ms 17532 KB Output is correct
27 Correct 464 ms 17568 KB Output is correct
28 Correct 210 ms 20108 KB Output is correct
29 Correct 245 ms 16076 KB Output is correct
30 Correct 434 ms 18240 KB Output is correct
31 Correct 684 ms 18124 KB Output is correct
32 Correct 443 ms 18096 KB Output is correct
33 Correct 314 ms 17020 KB Output is correct
34 Correct 377 ms 17072 KB Output is correct
35 Correct 471 ms 17576 KB Output is correct
36 Correct 199 ms 16056 KB Output is correct
37 Correct 654 ms 18140 KB Output is correct
38 Correct 252 ms 16268 KB Output is correct
39 Correct 412 ms 17212 KB Output is correct
40 Correct 363 ms 17064 KB Output is correct
41 Runtime error 16 ms 18680 KB Execution killed with signal 11
42 Halted 0 ms 0 KB -