답안 #564020

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
564020	2022-05-18T12:39:32 Z	SeDunion	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	686 ms	11888 KB

snake_escaping

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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	394 ms	4548 KB	Output is correct
12	Correct	421 ms	4044 KB	Output is correct
13	Correct	269 ms	3284 KB	Output is correct
14	Correct	263 ms	3408 KB	Output is correct
15	Correct	655 ms	6820 KB	Output is correct
16	Correct	371 ms	5508 KB	Output is correct
17	Correct	358 ms	5460 KB	Output is correct
18	Correct	177 ms	7400 KB	Output is correct
19	Correct	203 ms	4388 KB	Output is correct
20	Correct	435 ms	5968 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	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	394 ms	4548 KB	Output is correct
12	Correct	421 ms	4044 KB	Output is correct
13	Correct	269 ms	3284 KB	Output is correct
14	Correct	263 ms	3408 KB	Output is correct
15	Correct	655 ms	6820 KB	Output is correct
16	Correct	371 ms	5508 KB	Output is correct
17	Correct	358 ms	5460 KB	Output is correct
18	Correct	177 ms	7400 KB	Output is correct
19	Correct	203 ms	4388 KB	Output is correct
20	Correct	435 ms	5968 KB	Output is correct
21	Correct	236 ms	6436 KB	Output is correct
22	Correct	590 ms	6556 KB	Output is correct
23	Correct	386 ms	5700 KB	Output is correct
24	Correct	355 ms	5556 KB	Output is correct
25	Correct	290 ms	7372 KB	Output is correct
26	Correct	487 ms	6064 KB	Output is correct
27	Correct	462 ms	5952 KB	Output is correct
28	Correct	186 ms	8400 KB	Output is correct
29	Correct	221 ms	4436 KB	Output is correct
30	Correct	416 ms	6712 KB	Output is correct
31	Correct	686 ms	6468 KB	Output is correct
32	Correct	454 ms	6444 KB	Output is correct
33	Correct	307 ms	5472 KB	Output is correct
34	Correct	366 ms	5120 KB	Output is correct
35	Correct	455 ms	5532 KB	Output is correct
36	Correct	180 ms	3768 KB	Output is correct
37	Correct	644 ms	5604 KB	Output is correct
38	Correct	231 ms	3416 KB	Output is correct
39	Correct	387 ms	4800 KB	Output is correct
40	Correct	352 ms	4172 KB	Output is correct

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	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	58 ms	10864 KB	Output is correct
12	Incorrect	47 ms	11888 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	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	394 ms	4548 KB	Output is correct
12	Correct	421 ms	4044 KB	Output is correct
13	Correct	269 ms	3284 KB	Output is correct
14	Correct	263 ms	3408 KB	Output is correct
15	Correct	655 ms	6820 KB	Output is correct
16	Correct	371 ms	5508 KB	Output is correct
17	Correct	358 ms	5460 KB	Output is correct
18	Correct	177 ms	7400 KB	Output is correct
19	Correct	203 ms	4388 KB	Output is correct
20	Correct	435 ms	5968 KB	Output is correct
21	Correct	236 ms	6436 KB	Output is correct
22	Correct	590 ms	6556 KB	Output is correct
23	Correct	386 ms	5700 KB	Output is correct
24	Correct	355 ms	5556 KB	Output is correct
25	Correct	290 ms	7372 KB	Output is correct
26	Correct	487 ms	6064 KB	Output is correct
27	Correct	462 ms	5952 KB	Output is correct
28	Correct	186 ms	8400 KB	Output is correct
29	Correct	221 ms	4436 KB	Output is correct
30	Correct	416 ms	6712 KB	Output is correct
31	Correct	686 ms	6468 KB	Output is correct
32	Correct	454 ms	6444 KB	Output is correct
33	Correct	307 ms	5472 KB	Output is correct
34	Correct	366 ms	5120 KB	Output is correct
35	Correct	455 ms	5532 KB	Output is correct
36	Correct	180 ms	3768 KB	Output is correct
37	Correct	644 ms	5604 KB	Output is correct
38	Correct	231 ms	3416 KB	Output is correct
39	Correct	387 ms	4800 KB	Output is correct
40	Correct	352 ms	4172 KB	Output is correct
41	Correct	58 ms	10864 KB	Output is correct
42	Incorrect	47 ms	11888 KB	Output isn't correct
43	Halted	0 ms	0 KB	-

답안 #564020

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 0 / 53.0

Subtask #5 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
10.0 / 10.0

Subtask #4
0 / 53.0

Subtask #5
0 / 25.0