oj.uz

Submission #564021

# Submission time Handle Problem Language Result Execution time Memory
564021 2022-05-18T12:40:48 Z SeDunion Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 696 ms 19420 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 = 2e6 + 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 {
			assert(false);
			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 0 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 0 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 415 ms 4388 KB Output is correct
12 Correct 421 ms 4056 KB Output is correct
13 Correct 267 ms 3280 KB Output is correct
14 Correct 260 ms 3316 KB Output is correct
15 Correct 665 ms 4316 KB Output is correct
16 Correct 357 ms 3456 KB Output is correct
17 Correct 343 ms 3500 KB Output is correct
18 Correct 179 ms 5340 KB Output is correct
19 Correct 195 ms 2236 KB Output is correct
20 Correct 425 ms 3888 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 0 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 415 ms 4388 KB Output is correct
12 Correct 421 ms 4056 KB Output is correct
13 Correct 267 ms 3280 KB Output is correct
14 Correct 260 ms 3316 KB Output is correct
15 Correct 665 ms 4316 KB Output is correct
16 Correct 357 ms 3456 KB Output is correct
17 Correct 343 ms 3500 KB Output is correct
18 Correct 179 ms 5340 KB Output is correct
19 Correct 195 ms 2236 KB Output is correct
20 Correct 425 ms 3888 KB Output is correct
21 Correct 230 ms 4300 KB Output is correct
22 Correct 569 ms 4580 KB Output is correct
23 Correct 376 ms 3488 KB Output is correct
24 Correct 350 ms 3428 KB Output is correct
25 Correct 281 ms 5380 KB Output is correct
26 Correct 468 ms 3836 KB Output is correct
27 Correct 452 ms 3824 KB Output is correct
28 Correct 192 ms 6348 KB Output is correct
29 Correct 224 ms 2416 KB Output is correct
30 Correct 419 ms 4508 KB Output is correct
31 Correct 696 ms 4392 KB Output is correct
32 Correct 455 ms 4428 KB Output is correct
33 Correct 291 ms 3288 KB Output is correct
34 Correct 360 ms 3432 KB Output is correct
35 Correct 451 ms 3772 KB Output is correct
36 Correct 184 ms 2464 KB Output is correct
37 Correct 656 ms 4428 KB Output is correct
38 Correct 232 ms 2408 KB Output is correct
39 Correct 381 ms 3664 KB Output is correct
40 Correct 356 ms 3376 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 0 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 44 ms 9836 KB Output is correct
12 Runtime error 42 ms 19420 KB Execution killed with signal 6
13 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 0 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 415 ms 4388 KB Output is correct
12 Correct 421 ms 4056 KB Output is correct
13 Correct 267 ms 3280 KB Output is correct
14 Correct 260 ms 3316 KB Output is correct
15 Correct 665 ms 4316 KB Output is correct
16 Correct 357 ms 3456 KB Output is correct
17 Correct 343 ms 3500 KB Output is correct
18 Correct 179 ms 5340 KB Output is correct
19 Correct 195 ms 2236 KB Output is correct
20 Correct 425 ms 3888 KB Output is correct
21 Correct 230 ms 4300 KB Output is correct
22 Correct 569 ms 4580 KB Output is correct
23 Correct 376 ms 3488 KB Output is correct
24 Correct 350 ms 3428 KB Output is correct
25 Correct 281 ms 5380 KB Output is correct
26 Correct 468 ms 3836 KB Output is correct
27 Correct 452 ms 3824 KB Output is correct
28 Correct 192 ms 6348 KB Output is correct
29 Correct 224 ms 2416 KB Output is correct
30 Correct 419 ms 4508 KB Output is correct
31 Correct 696 ms 4392 KB Output is correct
32 Correct 455 ms 4428 KB Output is correct
33 Correct 291 ms 3288 KB Output is correct
34 Correct 360 ms 3432 KB Output is correct
35 Correct 451 ms 3772 KB Output is correct
36 Correct 184 ms 2464 KB Output is correct
37 Correct 656 ms 4428 KB Output is correct
38 Correct 232 ms 2408 KB Output is correct
39 Correct 381 ms 3664 KB Output is correct
40 Correct 356 ms 3376 KB Output is correct
41 Correct 44 ms 9836 KB Output is correct
42 Runtime error 42 ms 19420 KB Execution killed with signal 6
43 Halted 0 ms 0 KB -