oj.uz

Submission #860636

# Submission time Handle Problem Language Result Execution time Memory
860636 2023-10-13T15:04:40 Z phoenix0423 Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 554 ms 38008 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int maxn = 1<<20 + 5;
const int sqrtn = 500;
int super[maxn], sub[maxn];
//sos dp + sqrt-sort technique(pigeonhole principle)

int main(void){
	fastio;
	int l, q;
	cin>>l>>q;
	string s;
	cin>>s;
	for(int i = 0; i < (1 << l); i++) sub[i] = super[i] = s[i] - '0';
	for(int i = 0; i < l; i++){
		for(int mask = 0; mask < (1 << l); mask++){
			if(mask & (1 << i)) sub[mask] += sub[mask ^ (1 << i)];
			else super[mask] += super[mask ^ (1 << i)];
		}
	}
	while(q--){
		string t;
		cin>>t;
		int cnt0 = 0, cnt1 = 0, cnt2 = 0;
		int a = 0, b = 0, c = 0; //a = 0, b = 1, c = 2
		for(int i = 0; i < l; i++){
			char x = t[i];
			if(x == '0') cnt0++, a |= (1 << (l - i - 1));
			else if(x == '1') cnt1++, b |= (1 << (l - i - 1));
			else cnt2++, c |= (1 << (l - i - 1));
		}
		int ans = 0;
		if(cnt2 <= cnt0 && cnt2 <= cnt1){
			for(int mask = c; mask > 0; mask = (mask - 1) & c){
				ans += s[mask | b] - '0';
			}
			ans += s[b] - '0';
		}
		else if(cnt0 <= cnt1){
			for(int mask = a; mask > 0; mask = (mask - 1) & a){
				ans += (1 - 2 * (__builtin_popcount(mask) & 1)) * super[mask | b];
			}
			ans += super[b];
		}
		else{
			for(int mask = b; mask > 0; mask = (mask - 1) & b){
				ans += (1 - 2 * (__builtin_popcount(mask) & 1)) * sub[c | (b ^ mask)];
			}
			ans += sub[c | b];
		}
		cout<<ans<<"\n";
	}
}

Compilation message

snake_escaping.cpp:11:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   11 | const int maxn = 1<<20 + 5;
      |                     ~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2480 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2480 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 159 ms 6480 KB Output is correct
12 Correct 170 ms 6020 KB Output is correct
13 Correct 192 ms 5200 KB Output is correct
14 Correct 226 ms 5352 KB Output is correct
15 Correct 177 ms 6480 KB Output is correct
16 Correct 203 ms 5460 KB Output is correct
17 Correct 204 ms 6044 KB Output is correct
18 Correct 137 ms 7508 KB Output is correct
19 Correct 155 ms 4432 KB Output is correct
20 Correct 168 ms 5984 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2480 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 159 ms 6480 KB Output is correct
12 Correct 170 ms 6020 KB Output is correct
13 Correct 192 ms 5200 KB Output is correct
14 Correct 226 ms 5352 KB Output is correct
15 Correct 177 ms 6480 KB Output is correct
16 Correct 203 ms 5460 KB Output is correct
17 Correct 204 ms 6044 KB Output is correct
18 Correct 137 ms 7508 KB Output is correct
19 Correct 155 ms 4432 KB Output is correct
20 Correct 168 ms 5984 KB Output is correct
21 Correct 195 ms 6524 KB Output is correct
22 Correct 205 ms 6996 KB Output is correct
23 Correct 228 ms 5712 KB Output is correct
24 Correct 219 ms 5532 KB Output is correct
25 Correct 203 ms 7376 KB Output is correct
26 Correct 242 ms 6228 KB Output is correct
27 Correct 233 ms 5988 KB Output is correct
28 Correct 147 ms 8528 KB Output is correct
29 Correct 175 ms 4532 KB Output is correct
30 Correct 190 ms 6480 KB Output is correct
31 Correct 228 ms 6484 KB Output is correct
32 Correct 289 ms 6344 KB Output is correct
33 Correct 194 ms 5204 KB Output is correct
34 Correct 228 ms 5500 KB Output is correct
35 Correct 236 ms 6228 KB Output is correct
36 Correct 141 ms 4368 KB Output is correct
37 Correct 175 ms 6376 KB Output is correct
38 Correct 218 ms 4436 KB Output is correct
39 Correct 216 ms 5664 KB Output is correct
40 Correct 211 ms 5460 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2480 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 37 ms 12288 KB Output is correct
12 Correct 33 ms 13620 KB Output is correct
13 Correct 37 ms 13568 KB Output is correct
14 Correct 55 ms 13868 KB Output is correct
15 Correct 34 ms 13808 KB Output is correct
16 Correct 44 ms 13564 KB Output is correct
17 Correct 39 ms 13556 KB Output is correct
18 Correct 30 ms 13764 KB Output is correct
19 Correct 35 ms 13900 KB Output is correct
20 Correct 34 ms 13808 KB Output is correct
21 Correct 37 ms 13808 KB Output is correct
22 Correct 46 ms 13552 KB Output is correct
23 Correct 34 ms 13556 KB Output is correct
24 Correct 44 ms 13840 KB Output is correct
25 Correct 49 ms 13560 KB Output is correct
26 Correct 30 ms 13556 KB Output is correct
27 Correct 33 ms 13808 KB Output is correct
28 Correct 36 ms 13552 KB Output is correct
29 Correct 35 ms 13672 KB Output is correct
30 Correct 39 ms 13708 KB Output is correct
31 Correct 39 ms 13592 KB Output is correct
32 Correct 44 ms 13708 KB Output is correct
33 Correct 40 ms 13556 KB Output is correct
34 Correct 28 ms 13592 KB Output is correct
35 Correct 43 ms 13556 KB Output is correct
36 Correct 50 ms 13524 KB Output is correct
37 Correct 38 ms 13552 KB Output is correct
38 Correct 37 ms 13556 KB Output is correct
39 Correct 39 ms 13624 KB Output is correct
40 Correct 37 ms 13556 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2480 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 159 ms 6480 KB Output is correct
12 Correct 170 ms 6020 KB Output is correct
13 Correct 192 ms 5200 KB Output is correct
14 Correct 226 ms 5352 KB Output is correct
15 Correct 177 ms 6480 KB Output is correct
16 Correct 203 ms 5460 KB Output is correct
17 Correct 204 ms 6044 KB Output is correct
18 Correct 137 ms 7508 KB Output is correct
19 Correct 155 ms 4432 KB Output is correct
20 Correct 168 ms 5984 KB Output is correct
21 Correct 195 ms 6524 KB Output is correct
22 Correct 205 ms 6996 KB Output is correct
23 Correct 228 ms 5712 KB Output is correct
24 Correct 219 ms 5532 KB Output is correct
25 Correct 203 ms 7376 KB Output is correct
26 Correct 242 ms 6228 KB Output is correct
27 Correct 233 ms 5988 KB Output is correct
28 Correct 147 ms 8528 KB Output is correct
29 Correct 175 ms 4532 KB Output is correct
30 Correct 190 ms 6480 KB Output is correct
31 Correct 228 ms 6484 KB Output is correct
32 Correct 289 ms 6344 KB Output is correct
33 Correct 194 ms 5204 KB Output is correct
34 Correct 228 ms 5500 KB Output is correct
35 Correct 236 ms 6228 KB Output is correct
36 Correct 141 ms 4368 KB Output is correct
37 Correct 175 ms 6376 KB Output is correct
38 Correct 218 ms 4436 KB Output is correct
39 Correct 216 ms 5664 KB Output is correct
40 Correct 211 ms 5460 KB Output is correct
41 Correct 37 ms 12288 KB Output is correct
42 Correct 33 ms 13620 KB Output is correct
43 Correct 37 ms 13568 KB Output is correct
44 Correct 55 ms 13868 KB Output is correct
45 Correct 34 ms 13808 KB Output is correct
46 Correct 44 ms 13564 KB Output is correct
47 Correct 39 ms 13556 KB Output is correct
48 Correct 30 ms 13764 KB Output is correct
49 Correct 35 ms 13900 KB Output is correct
50 Correct 34 ms 13808 KB Output is correct
51 Correct 37 ms 13808 KB Output is correct
52 Correct 46 ms 13552 KB Output is correct
53 Correct 34 ms 13556 KB Output is correct
54 Correct 44 ms 13840 KB Output is correct
55 Correct 49 ms 13560 KB Output is correct
56 Correct 30 ms 13556 KB Output is correct
57 Correct 33 ms 13808 KB Output is correct
58 Correct 36 ms 13552 KB Output is correct
59 Correct 35 ms 13672 KB Output is correct
60 Correct 39 ms 13708 KB Output is correct
61 Correct 39 ms 13592 KB Output is correct
62 Correct 44 ms 13708 KB Output is correct
63 Correct 40 ms 13556 KB Output is correct
64 Correct 28 ms 13592 KB Output is correct
65 Correct 43 ms 13556 KB Output is correct
66 Correct 50 ms 13524 KB Output is correct
67 Correct 38 ms 13552 KB Output is correct
68 Correct 37 ms 13556 KB Output is correct
69 Correct 39 ms 13624 KB Output is correct
70 Correct 37 ms 13556 KB Output is correct
71 Correct 292 ms 36196 KB Output is correct
72 Correct 296 ms 28640 KB Output is correct
73 Correct 349 ms 27120 KB Output is correct
74 Correct 554 ms 27120 KB Output is correct
75 Correct 310 ms 34692 KB Output is correct
76 Correct 511 ms 28008 KB Output is correct
77 Correct 422 ms 27544 KB Output is correct
78 Correct 219 ms 35516 KB Output is correct
79 Correct 289 ms 25328 KB Output is correct
80 Correct 291 ms 38008 KB Output is correct
81 Correct 368 ms 32324 KB Output is correct
82 Correct 545 ms 27824 KB Output is correct
83 Correct 290 ms 26516 KB Output is correct
84 Correct 400 ms 27480 KB Output is correct
85 Correct 435 ms 27536 KB Output is correct
86 Correct 206 ms 25072 KB Output is correct
87 Correct 272 ms 31496 KB Output is correct
88 Correct 274 ms 25076 KB Output is correct
89 Correct 323 ms 25408 KB Output is correct
90 Correct 382 ms 16204 KB Output is correct
91 Correct 301 ms 15088 KB Output is correct
92 Correct 446 ms 19884 KB Output is correct
93 Correct 402 ms 18672 KB Output is correct
94 Correct 189 ms 13932 KB Output is correct
95 Correct 401 ms 21708 KB Output is correct
96 Correct 368 ms 19812 KB Output is correct
97 Correct 357 ms 19680 KB Output is correct
98 Correct 368 ms 20208 KB Output is correct
99 Correct 372 ms 20632 KB Output is correct
100 Correct 363 ms 22016 KB Output is correct