Submission #564012

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
564012	2022-05-18T12:26:07 Z	SeDunion	Snake Escaping (JOI18_snake_escaping)	C++17	5 / 100	2000 ms	19872 KB

snake_escaping

#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;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int L, q;
	cin >> L >> q;
	string vals;
	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];
			}
		}
	}
	string qs;
	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();
			for (int m = 0 ; m < (1 << n) ; ++ m) {
				int l = 0;
				int mask = 0;
				for (int i = 0 ; i < L ; ++ i) {
					if (qs[i] == '1') {
						mask |= 1 << i;
					} else if (qs[i] == '?') {
						if (m >> l & 1) mask |= 1 << i;
						++l;
					}
				}
				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();
			for (int m = 0 ; m < (1 << n) ; ++ m) {
				int l = 0;
				int mask = 0;
				for (int i = 0 ; i < L ; ++ i) {
					if (qs[i] == '1') {
						mask |= 1 << i;
					} else if (qs[i] == '0') {
						if (m >> l & 1) mask |= 1 << i;
						++l;
					}
				}
				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();
			for (int m = 0 ; m < (1 << n) ; ++ m) {
				int l = 0;
				int mask = 0;
				for (int i = 0 ; i < L ; ++ i) {
					if (qs[i] == '?') {
						mask |= 1 << i;
					} else if (qs[i] == '1') {
						if (m >> l & 1) mask |= 1 << i;
						++l;
					}
				}
				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	2 ms	340 KB	Output is correct
2	Correct	2 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	5 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 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	2 ms	340 KB	Output is correct

Subtask #2

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 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	5 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 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	2 ms	340 KB	Output is correct
11	Correct	1924 ms	15056 KB	Output is correct
12	Correct	1712 ms	14660 KB	Output is correct
13	Correct	694 ms	13988 KB	Output is correct
14	Correct	779 ms	13980 KB	Output is correct
15	Execution timed out	2074 ms	8412 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 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	5 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 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	2 ms	340 KB	Output is correct
11	Correct	1924 ms	15056 KB	Output is correct
12	Correct	1712 ms	14660 KB	Output is correct
13	Correct	694 ms	13988 KB	Output is correct
14	Correct	779 ms	13980 KB	Output is correct
15	Execution timed out	2074 ms	8412 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-

Subtask #4

0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 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	5 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 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	2 ms	340 KB	Output is correct
11	Runtime error	16 ms	19872 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	2 ms	340 KB	Output is correct
2	Correct	2 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	5 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 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	2 ms	340 KB	Output is correct
11	Correct	1924 ms	15056 KB	Output is correct
12	Correct	1712 ms	14660 KB	Output is correct
13	Correct	694 ms	13988 KB	Output is correct
14	Correct	779 ms	13980 KB	Output is correct
15	Execution timed out	2074 ms	8412 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-