oj.uz

Submission #598642

# Submission time Handle Problem Language Result Execution time Memory
598642 2022-07-18T15:49:37 Z Asymmetry Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 1127 ms 42312 KB 
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<'\n';}(x)
#else
#define debug(...) {}
#endif

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int L, Q;
	cin >> L >> Q;
	vector<int> t(1 << L);
	for (int &i : t) {
		char c;
		cin >> c;
		i = c - '0';
	}
	auto r = t;
	REP (i, 1 << L) {
		if (i < (i ^ ((1 << L) - 1))) {
			swap(r[i], r[i ^ ((1 << L) - 1)]);
		}
	}

	auto SOS = [&](vector<int> &v) {
		REP (i, L) {
			REP (j, 1 << L) {
				if (j & (1 << i)) {
					v[j] += v[j ^ (1 << i)];
				}
			}
		}
	};
	
	auto v = t;
	SOS(v);
	SOS(r);
	
	map<char, int> mp;
	mp['0'] = 0;
	mp['1'] = 1;
	mp['?'] = 2;
	REP (i, Q) {
		vector<char> w(L);
		vector<int> z(3);
		for (char &j : w) {
			cin >> j;
			++z[mp[j]];
		}
		reverse(w.begin(), w.end());
		if (z[0] < 7) {
			int odp = 0, bas = 0, msk = 0;
			REP (j, L) {
				if (w[j] == '?') {
					bas ^= 1 << j;
				}
				else if (w[j] == '0') {
					msk ^= 1 << j;
				}
			}
			for (int j = msk; j; j = (j - 1) & msk) {
				if (__builtin_parity(msk ^ j)) {
					odp -= r[j ^ bas];
				}
				else {
					odp += r[j ^ bas];
				}
			}
			cout << odp + (__builtin_parity(msk) ? -r[bas] : r[bas]) << '\n';
		}
		else if (z[1] < 7) {
			int odp = 0, bas = 0, msk = 0;
			REP (j, L) {
				if (w[j] == '?') {
					bas ^= 1 << j;
				}
				else if (w[j] == '1') {
					msk ^= 1 << j;
				}
			}
			for (int j = msk; j; j = (j - 1) & msk) {
				if (__builtin_parity(msk ^ j)) {
					odp -= v[j ^ bas];
				}
				else {
					odp += v[j ^ bas];
				}
			}
			cout << odp + (__builtin_parity(msk) ? -v[bas] : v[bas]) << '\n';
		}
		else {
			int odp = 0, bas = 0, msk = 0;
			REP (j, L) {
				if (w[j] == '?') {
					msk ^= 1 << j;
				}
				else if (w[j] == '1') {
					bas ^= 1 << j;
				}
			}
			for (int j = msk; j; j = (j - 1) & msk) {
				odp += t[bas ^ j];
			}
			cout << odp + t[bas] << '\n';
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 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 324 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 328 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 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 324 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 383 ms 15028 KB Output is correct
12 Correct 433 ms 14712 KB Output is correct
13 Correct 427 ms 13956 KB Output is correct
14 Correct 434 ms 14028 KB Output is correct
15 Correct 411 ms 15048 KB Output is correct
16 Correct 442 ms 14168 KB Output is correct
17 Correct 427 ms 14228 KB Output is correct
18 Correct 313 ms 16056 KB Output is correct
19 Correct 409 ms 13044 KB Output is correct
20 Correct 382 ms 14764 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 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 324 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 383 ms 15028 KB Output is correct
12 Correct 433 ms 14712 KB Output is correct
13 Correct 427 ms 13956 KB Output is correct
14 Correct 434 ms 14028 KB Output is correct
15 Correct 411 ms 15048 KB Output is correct
16 Correct 442 ms 14168 KB Output is correct
17 Correct 427 ms 14228 KB Output is correct
18 Correct 313 ms 16056 KB Output is correct
19 Correct 409 ms 13044 KB Output is correct
20 Correct 382 ms 14764 KB Output is correct
21 Correct 461 ms 18144 KB Output is correct
22 Correct 531 ms 18380 KB Output is correct
23 Correct 610 ms 17308 KB Output is correct
24 Correct 562 ms 17112 KB Output is correct
25 Correct 569 ms 19092 KB Output is correct
26 Correct 707 ms 17532 KB Output is correct
27 Correct 578 ms 17536 KB Output is correct
28 Correct 386 ms 20144 KB Output is correct
29 Correct 553 ms 16152 KB Output is correct
30 Correct 470 ms 18380 KB Output is correct
31 Correct 564 ms 18240 KB Output is correct
32 Correct 513 ms 18108 KB Output is correct
33 Correct 437 ms 17020 KB Output is correct
34 Correct 537 ms 17076 KB Output is correct
35 Correct 552 ms 17556 KB Output is correct
36 Correct 336 ms 16076 KB Output is correct
37 Correct 489 ms 18104 KB Output is correct
38 Correct 513 ms 16044 KB Output is correct
39 Correct 499 ms 17388 KB Output is correct
40 Correct 552 ms 17240 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 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 324 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 139 ms 14912 KB Output is correct
12 Correct 135 ms 14928 KB Output is correct
13 Correct 150 ms 14804 KB Output is correct
14 Correct 142 ms 14800 KB Output is correct
15 Correct 141 ms 14988 KB Output is correct
16 Correct 147 ms 14856 KB Output is correct
17 Correct 153 ms 14792 KB Output is correct
18 Correct 121 ms 15036 KB Output is correct
19 Correct 129 ms 14812 KB Output is correct
20 Correct 128 ms 14920 KB Output is correct
21 Correct 137 ms 14912 KB Output is correct
22 Correct 143 ms 14796 KB Output is correct
23 Correct 136 ms 14924 KB Output is correct
24 Correct 150 ms 14804 KB Output is correct
25 Correct 153 ms 14796 KB Output is correct
26 Correct 130 ms 14668 KB Output is correct
27 Correct 135 ms 14924 KB Output is correct
28 Correct 127 ms 14680 KB Output is correct
29 Correct 137 ms 14788 KB Output is correct
30 Correct 144 ms 14784 KB Output is correct
31 Correct 129 ms 14804 KB Output is correct
32 Correct 152 ms 14916 KB Output is correct
33 Correct 150 ms 14800 KB Output is correct
34 Correct 136 ms 14668 KB Output is correct
35 Correct 138 ms 14796 KB Output is correct
36 Correct 138 ms 14796 KB Output is correct
37 Correct 139 ms 14884 KB Output is correct
38 Correct 160 ms 14940 KB Output is correct
39 Correct 140 ms 14796 KB Output is correct
40 Correct 140 ms 14796 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 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 324 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 383 ms 15028 KB Output is correct
12 Correct 433 ms 14712 KB Output is correct
13 Correct 427 ms 13956 KB Output is correct
14 Correct 434 ms 14028 KB Output is correct
15 Correct 411 ms 15048 KB Output is correct
16 Correct 442 ms 14168 KB Output is correct
17 Correct 427 ms 14228 KB Output is correct
18 Correct 313 ms 16056 KB Output is correct
19 Correct 409 ms 13044 KB Output is correct
20 Correct 382 ms 14764 KB Output is correct
21 Correct 461 ms 18144 KB Output is correct
22 Correct 531 ms 18380 KB Output is correct
23 Correct 610 ms 17308 KB Output is correct
24 Correct 562 ms 17112 KB Output is correct
25 Correct 569 ms 19092 KB Output is correct
26 Correct 707 ms 17532 KB Output is correct
27 Correct 578 ms 17536 KB Output is correct
28 Correct 386 ms 20144 KB Output is correct
29 Correct 553 ms 16152 KB Output is correct
30 Correct 470 ms 18380 KB Output is correct
31 Correct 564 ms 18240 KB Output is correct
32 Correct 513 ms 18108 KB Output is correct
33 Correct 437 ms 17020 KB Output is correct
34 Correct 537 ms 17076 KB Output is correct
35 Correct 552 ms 17556 KB Output is correct
36 Correct 336 ms 16076 KB Output is correct
37 Correct 489 ms 18104 KB Output is correct
38 Correct 513 ms 16044 KB Output is correct
39 Correct 499 ms 17388 KB Output is correct
40 Correct 552 ms 17240 KB Output is correct
41 Correct 139 ms 14912 KB Output is correct
42 Correct 135 ms 14928 KB Output is correct
43 Correct 150 ms 14804 KB Output is correct
44 Correct 142 ms 14800 KB Output is correct
45 Correct 141 ms 14988 KB Output is correct
46 Correct 147 ms 14856 KB Output is correct
47 Correct 153 ms 14792 KB Output is correct
48 Correct 121 ms 15036 KB Output is correct
49 Correct 129 ms 14812 KB Output is correct
50 Correct 128 ms 14920 KB Output is correct
51 Correct 137 ms 14912 KB Output is correct
52 Correct 143 ms 14796 KB Output is correct
53 Correct 136 ms 14924 KB Output is correct
54 Correct 150 ms 14804 KB Output is correct
55 Correct 153 ms 14796 KB Output is correct
56 Correct 130 ms 14668 KB Output is correct
57 Correct 135 ms 14924 KB Output is correct
58 Correct 127 ms 14680 KB Output is correct
59 Correct 137 ms 14788 KB Output is correct
60 Correct 144 ms 14784 KB Output is correct
61 Correct 129 ms 14804 KB Output is correct
62 Correct 152 ms 14916 KB Output is correct
63 Correct 150 ms 14800 KB Output is correct
64 Correct 136 ms 14668 KB Output is correct
65 Correct 138 ms 14796 KB Output is correct
66 Correct 138 ms 14796 KB Output is correct
67 Correct 139 ms 14884 KB Output is correct
68 Correct 160 ms 14940 KB Output is correct
69 Correct 140 ms 14796 KB Output is correct
70 Correct 140 ms 14796 KB Output is correct
71 Correct 839 ms 39216 KB Output is correct
72 Correct 839 ms 39272 KB Output is correct
73 Correct 913 ms 37804 KB Output is correct
74 Correct 993 ms 38204 KB Output is correct
75 Correct 833 ms 40196 KB Output is correct
76 Correct 1127 ms 38580 KB Output is correct
77 Correct 1119 ms 38460 KB Output is correct
78 Correct 583 ms 42312 KB Output is correct
79 Correct 683 ms 36224 KB Output is correct
80 Correct 773 ms 39328 KB Output is correct
81 Correct 906 ms 39132 KB Output is correct
82 Correct 957 ms 38276 KB Output is correct
83 Correct 712 ms 37412 KB Output is correct
84 Correct 1117 ms 38216 KB Output is correct
85 Correct 1063 ms 38412 KB Output is correct
86 Correct 542 ms 36232 KB Output is correct
87 Correct 772 ms 39188 KB Output is correct
88 Correct 738 ms 36164 KB Output is correct
89 Correct 837 ms 37860 KB Output is correct
90 Correct 915 ms 38196 KB Output is correct
91 Correct 755 ms 37336 KB Output is correct
92 Correct 1115 ms 38532 KB Output is correct
93 Correct 1108 ms 38416 KB Output is correct
94 Correct 605 ms 36188 KB Output is correct
95 Correct 1064 ms 38224 KB Output is correct
96 Correct 1020 ms 38292 KB Output is correct
97 Correct 964 ms 38256 KB Output is correct
98 Correct 995 ms 38328 KB Output is correct
99 Correct 1010 ms 38352 KB Output is correct
100 Correct 986 ms 38276 KB Output is correct