oj.uz

Submission #651529

# Submission time Handle Problem Language Result Execution time Memory
651529 2022-10-19T08:28:42 Z ymm Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 1539 ms 26200 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int L = 20;
int sub[1<<L];
int sup[1<<L];
int poi[1<<L];
int sign[1<<L];
int q, l;

void sos()
{
	Loop (i,0,1<<l) {
		sign[i] = __builtin_popcount(i)&1? -1: 0;
		sub[i] = poi[i];
		sup[i] = poi[i];
	}
	for (int i = 1; i < (1<<l); i <<= 1) {
		Loop (j,0,1<<l) {
			if (j&i) {
				sub[j] += sub[j^i];
				sup[j^i] += sup[j];
			}
		}
	}
}

#define SIGN(x, s) (((x)^(s))-(s))

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	string s;
	cin >> l >> q;
	cin >> s;
	Loop (i,0,1<<l)
		poi[i] = s[i]-'0';
	sos();
	while (q--) {
		int cnt[3]={}, msk[3]={};
		cin >> s;
		Loop (i,0,l) {
			char c = s[l-1-i];
			c = c =='?'? 2: c-'0';
			cnt[c]++;
			msk[c] ^= (1<<i);
		}
		int ans = 0;
		if (cnt[2] <= cnt[0] && cnt[2] <= cnt[0]) {
			int x = msk[2];
			Loop (i,0,1<<cnt[2]) {
				ans += poi[msk[1] ^ x];
				x = (x-1) & msk[2];
			}
		} else if (cnt[1] <= cnt[0] && cnt[1] <= cnt[2]) {
			int x = msk[1];
			Loop (i,0,1<<cnt[1]) {
				ans += SIGN(sub[msk[2]^x], sign[msk[1]^x]);
				x = (x-1) & msk[1];
			}
		} else {
			int x = msk[0];
			Loop (i,0,1<<cnt[0]) {
				ans += SIGN(sup[msk[1]^x], sign[x]);
				x = (x-1) & msk[0];
			}
		}
		cout << ans << '\n';
	}
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:50:8: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |    cnt[c]++;
      |        ^
snake_escaping.cpp:51:8: warning: array subscript has type 'char' [-Wchar-subscripts]
   51 |    msk[c] ^= (1<<i);
      |        ^

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 183 ms 15108 KB Output is correct
12 Correct 203 ms 14736 KB Output is correct
13 Correct 218 ms 14008 KB Output is correct
14 Correct 179 ms 14024 KB Output is correct
15 Correct 211 ms 15096 KB Output is correct
16 Correct 197 ms 14232 KB Output is correct
17 Correct 233 ms 14244 KB Output is correct
18 Correct 172 ms 16204 KB Output is correct
19 Correct 173 ms 13072 KB Output is correct
20 Correct 193 ms 14724 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 183 ms 15108 KB Output is correct
12 Correct 203 ms 14736 KB Output is correct
13 Correct 218 ms 14008 KB Output is correct
14 Correct 179 ms 14024 KB Output is correct
15 Correct 211 ms 15096 KB Output is correct
16 Correct 197 ms 14232 KB Output is correct
17 Correct 233 ms 14244 KB Output is correct
18 Correct 172 ms 16204 KB Output is correct
19 Correct 173 ms 13072 KB Output is correct
20 Correct 193 ms 14724 KB Output is correct
21 Correct 188 ms 17700 KB Output is correct
22 Correct 238 ms 18092 KB Output is correct
23 Correct 224 ms 16928 KB Output is correct
24 Correct 238 ms 16792 KB Output is correct
25 Correct 232 ms 18800 KB Output is correct
26 Correct 214 ms 17228 KB Output is correct
27 Correct 246 ms 17324 KB Output is correct
28 Correct 209 ms 19728 KB Output is correct
29 Correct 193 ms 15760 KB Output is correct
30 Correct 211 ms 17904 KB Output is correct
31 Correct 230 ms 17868 KB Output is correct
32 Correct 234 ms 17868 KB Output is correct
33 Correct 221 ms 16724 KB Output is correct
34 Correct 221 ms 16888 KB Output is correct
35 Correct 242 ms 17232 KB Output is correct
36 Correct 205 ms 15876 KB Output is correct
37 Correct 265 ms 17804 KB Output is correct
38 Correct 192 ms 15776 KB Output is correct
39 Correct 223 ms 16884 KB Output is correct
40 Correct 208 ms 16724 KB Output is correct

Subtask #4
53.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 Correct 47 ms 20168 KB Output is correct
12 Correct 75 ms 20112 KB Output is correct
13 Correct 54 ms 20008 KB Output is correct
14 Correct 54 ms 20032 KB Output is correct
15 Correct 47 ms 20200 KB Output is correct
16 Correct 59 ms 20124 KB Output is correct
17 Correct 66 ms 20140 KB Output is correct
18 Correct 55 ms 20208 KB Output is correct
19 Correct 45 ms 19952 KB Output is correct
20 Correct 46 ms 20128 KB Output is correct
21 Correct 47 ms 20076 KB Output is correct
22 Correct 66 ms 20032 KB Output is correct
23 Correct 54 ms 20036 KB Output is correct
24 Correct 61 ms 20120 KB Output is correct
25 Correct 58 ms 20076 KB Output is correct
26 Correct 43 ms 19948 KB Output is correct
27 Correct 110 ms 20124 KB Output is correct
28 Correct 54 ms 19920 KB Output is correct
29 Correct 47 ms 20036 KB Output is correct
30 Correct 50 ms 20040 KB Output is correct
31 Correct 46 ms 19996 KB Output is correct
32 Correct 63 ms 20076 KB Output is correct
33 Correct 64 ms 20040 KB Output is correct
34 Correct 46 ms 20028 KB Output is correct
35 Correct 64 ms 20072 KB Output is correct
36 Correct 60 ms 20036 KB Output is correct
37 Correct 58 ms 20144 KB Output is correct
38 Correct 54 ms 20044 KB Output is correct
39 Correct 54 ms 20076 KB Output is correct
40 Correct 63 ms 20132 KB Output is correct

Subtask #5
25.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 183 ms 15108 KB Output is correct
12 Correct 203 ms 14736 KB Output is correct
13 Correct 218 ms 14008 KB Output is correct
14 Correct 179 ms 14024 KB Output is correct
15 Correct 211 ms 15096 KB Output is correct
16 Correct 197 ms 14232 KB Output is correct
17 Correct 233 ms 14244 KB Output is correct
18 Correct 172 ms 16204 KB Output is correct
19 Correct 173 ms 13072 KB Output is correct
20 Correct 193 ms 14724 KB Output is correct
21 Correct 188 ms 17700 KB Output is correct
22 Correct 238 ms 18092 KB Output is correct
23 Correct 224 ms 16928 KB Output is correct
24 Correct 238 ms 16792 KB Output is correct
25 Correct 232 ms 18800 KB Output is correct
26 Correct 214 ms 17228 KB Output is correct
27 Correct 246 ms 17324 KB Output is correct
28 Correct 209 ms 19728 KB Output is correct
29 Correct 193 ms 15760 KB Output is correct
30 Correct 211 ms 17904 KB Output is correct
31 Correct 230 ms 17868 KB Output is correct
32 Correct 234 ms 17868 KB Output is correct
33 Correct 221 ms 16724 KB Output is correct
34 Correct 221 ms 16888 KB Output is correct
35 Correct 242 ms 17232 KB Output is correct
36 Correct 205 ms 15876 KB Output is correct
37 Correct 265 ms 17804 KB Output is correct
38 Correct 192 ms 15776 KB Output is correct
39 Correct 223 ms 16884 KB Output is correct
40 Correct 208 ms 16724 KB Output is correct
41 Correct 47 ms 20168 KB Output is correct
42 Correct 75 ms 20112 KB Output is correct
43 Correct 54 ms 20008 KB Output is correct
44 Correct 54 ms 20032 KB Output is correct
45 Correct 47 ms 20200 KB Output is correct
46 Correct 59 ms 20124 KB Output is correct
47 Correct 66 ms 20140 KB Output is correct
48 Correct 55 ms 20208 KB Output is correct
49 Correct 45 ms 19952 KB Output is correct
50 Correct 46 ms 20128 KB Output is correct
51 Correct 47 ms 20076 KB Output is correct
52 Correct 66 ms 20032 KB Output is correct
53 Correct 54 ms 20036 KB Output is correct
54 Correct 61 ms 20120 KB Output is correct
55 Correct 58 ms 20076 KB Output is correct
56 Correct 43 ms 19948 KB Output is correct
57 Correct 110 ms 20124 KB Output is correct
58 Correct 54 ms 19920 KB Output is correct
59 Correct 47 ms 20036 KB Output is correct
60 Correct 50 ms 20040 KB Output is correct
61 Correct 46 ms 19996 KB Output is correct
62 Correct 63 ms 20076 KB Output is correct
63 Correct 64 ms 20040 KB Output is correct
64 Correct 46 ms 20028 KB Output is correct
65 Correct 64 ms 20072 KB Output is correct
66 Correct 60 ms 20036 KB Output is correct
67 Correct 58 ms 20144 KB Output is correct
68 Correct 54 ms 20044 KB Output is correct
69 Correct 54 ms 20076 KB Output is correct
70 Correct 63 ms 20132 KB Output is correct
71 Correct 294 ms 23276 KB Output is correct
72 Correct 704 ms 23348 KB Output is correct
73 Correct 356 ms 22008 KB Output is correct
74 Correct 487 ms 22356 KB Output is correct
75 Correct 323 ms 24284 KB Output is correct
76 Correct 689 ms 22580 KB Output is correct
77 Correct 593 ms 22424 KB Output is correct
78 Correct 243 ms 26200 KB Output is correct
79 Correct 285 ms 20176 KB Output is correct
80 Correct 318 ms 23344 KB Output is correct
81 Correct 433 ms 23204 KB Output is correct
82 Correct 600 ms 22228 KB Output is correct
83 Correct 327 ms 21432 KB Output is correct
84 Correct 600 ms 22264 KB Output is correct
85 Correct 704 ms 22488 KB Output is correct
86 Correct 241 ms 20168 KB Output is correct
87 Correct 1539 ms 23256 KB Output is correct
88 Correct 290 ms 20292 KB Output is correct
89 Correct 375 ms 21860 KB Output is correct
90 Correct 467 ms 22124 KB Output is correct
91 Correct 327 ms 21216 KB Output is correct
92 Correct 661 ms 22396 KB Output is correct
93 Correct 526 ms 22356 KB Output is correct
94 Correct 234 ms 20032 KB Output is correct
95 Correct 530 ms 22076 KB Output is correct
96 Correct 515 ms 22196 KB Output is correct
97 Correct 521 ms 22116 KB Output is correct
98 Correct 488 ms 21976 KB Output is correct
99 Correct 553 ms 22180 KB Output is correct
100 Correct 537 ms 21960 KB Output is correct