oj.uz

Submission #332062

# Submission time Handle Problem Language Result Execution time Memory
332062 2020-12-01T10:45:32 Z AmShZ Snake Escaping (JOI18_snake_escaping) C++11
100 / 100
 1448 ms 26640 KB 
//khodaya khodet komak kon
# include <bits/stdc++.h>
 
/*
// ordered_set 
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
# define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
*/
 
using namespace std;
 
typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;
 
# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define lc                                              id << 1
# define rc                                              lc | 1
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define InTheNameOfGod                                  ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
 
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
 
const int xn = 21;
const int xm = - 20 + 10;
const int sq = 320;
const ll inf = 1e18 + 10;
const ll INF = 1e18 + 10;
const int mod = 998244353;
const int base = 257;

int n, q, a[1 << xn], cnt[3], ted[1 << xn];
pii dp[1 << xn];
string s;

void solve3(){
	int mask = 0, tot = 0, ans = 0;
	for (int i = 0; i < n; ++ i){
		if (s[i] == '?')
			mask += (1 << i);
		else
			tot += (s[i] - '0') * (1 << i);
	}
	for (int sub = mask; sub > 0; sub = ((sub - 1) & mask))
		ans += a[tot + sub];
	ans += a[tot];
	cout << ans << endl;
}
void solve2(){
	int tot = 0, ans = 0, mask = 0;
	for (int i = 0; i < n; ++ i){
		if (s[i] != '0')
			tot += (1 << i);
		if (s[i] == '1')
			mask += (1 << i);
	}
	ans = dp[tot].A;
	for (int sub = mask; sub > 0; sub = ((sub - 1) & mask)){
		if (ted[sub] % 2)
			ans -= dp[tot - sub].A;
		else
			ans += dp[tot - sub].A;
	}
	cout << ans << endl;
}
void solve1(){
	int tot = 0, ans = 0, mask = 0;
	for (int i = 0; i < n; ++ i){
		if (s[i] == '1')
			tot += (1 << i);
		else if (s[i] == '0')
			mask += (1 << i);
	}
	ans = dp[tot].B;
	for (int sub = mask; sub > 0; sub = ((sub - 1) & mask)){
		if (ted[sub] % 2)
			ans -= dp[tot + sub].B;
		else
			ans += dp[tot + sub].B;
	}
	cout << ans << endl;
}

int main(){
	InTheNameOfGod;
	
	cin >> n >> q >> s;
	for (int i = 0; i < (1 << n); ++ i)
		a[i] = dp[i].A = dp[i].B = s[i] - '0';
	for (int bit = 0; bit < n; ++ bit){
		for (int mask = (1 << n) - 1; mask >= 0; -- mask)
			if ((mask & (1 << bit)))
				dp[mask].A += dp[mask - (1 << bit)].A;
		for (int mask = 0; mask < (1 << n); ++ mask)
			if (!(mask & (1 << bit)))
				dp[mask].B += dp[mask + (1 << bit)].B;
	}
	for (int mask = 1; mask < (1 << n); ++ mask)
		ted[mask] = __builtin_popcount(mask);
	while (q --){
		cin >> s, reverse(all(s));
		cnt[0] = cnt[1] = cnt[2] = 0;
		for (char c : s){
			if (c == '0')
				++ cnt[0];
			else if (c == '1')
				++ cnt[1];
			else
				++ cnt[2];
		}
		if (cnt[0] <= n / 3)
			solve1();
		else if (cnt[1] <= n / 3)
			solve2();
		else
			solve3();
	}
	
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 291 ms 6764 KB Output is correct
12 Correct 288 ms 6252 KB Output is correct
13 Correct 338 ms 5740 KB Output is correct
14 Correct 315 ms 5636 KB Output is correct
15 Correct 305 ms 6636 KB Output is correct
16 Correct 360 ms 5868 KB Output is correct
17 Correct 366 ms 5740 KB Output is correct
18 Correct 238 ms 7660 KB Output is correct
19 Correct 260 ms 4716 KB Output is correct
20 Correct 307 ms 6532 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 291 ms 6764 KB Output is correct
12 Correct 288 ms 6252 KB Output is correct
13 Correct 338 ms 5740 KB Output is correct
14 Correct 315 ms 5636 KB Output is correct
15 Correct 305 ms 6636 KB Output is correct
16 Correct 360 ms 5868 KB Output is correct
17 Correct 366 ms 5740 KB Output is correct
18 Correct 238 ms 7660 KB Output is correct
19 Correct 260 ms 4716 KB Output is correct
20 Correct 307 ms 6532 KB Output is correct
21 Correct 339 ms 7148 KB Output is correct
22 Correct 385 ms 7276 KB Output is correct
23 Correct 407 ms 6252 KB Output is correct
24 Correct 428 ms 6124 KB Output is correct
25 Correct 362 ms 8064 KB Output is correct
26 Correct 488 ms 6680 KB Output is correct
27 Correct 444 ms 6544 KB Output is correct
28 Correct 256 ms 9196 KB Output is correct
29 Correct 294 ms 4972 KB Output is correct
30 Correct 376 ms 7040 KB Output is correct
31 Correct 442 ms 7020 KB Output is correct
32 Correct 455 ms 6764 KB Output is correct
33 Correct 380 ms 5484 KB Output is correct
34 Correct 435 ms 5612 KB Output is correct
35 Correct 460 ms 6252 KB Output is correct
36 Correct 253 ms 4460 KB Output is correct
37 Correct 336 ms 6380 KB Output is correct
38 Correct 351 ms 4460 KB Output is correct
39 Correct 399 ms 5740 KB Output is correct
40 Correct 421 ms 5228 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 95 ms 19088 KB Output is correct
12 Correct 94 ms 18960 KB Output is correct
13 Correct 109 ms 18832 KB Output is correct
14 Correct 144 ms 18832 KB Output is correct
15 Correct 95 ms 18960 KB Output is correct
16 Correct 142 ms 18832 KB Output is correct
17 Correct 116 ms 18832 KB Output is correct
18 Correct 78 ms 18960 KB Output is correct
19 Correct 86 ms 18704 KB Output is correct
20 Correct 92 ms 18832 KB Output is correct
21 Correct 103 ms 18832 KB Output is correct
22 Correct 132 ms 18704 KB Output is correct
23 Correct 98 ms 18832 KB Output is correct
24 Correct 122 ms 18832 KB Output is correct
25 Correct 123 ms 18832 KB Output is correct
26 Correct 84 ms 18704 KB Output is correct
27 Correct 96 ms 18832 KB Output is correct
28 Correct 114 ms 18704 KB Output is correct
29 Correct 111 ms 18704 KB Output is correct
30 Correct 103 ms 18704 KB Output is correct
31 Correct 97 ms 18704 KB Output is correct
32 Correct 126 ms 18832 KB Output is correct
33 Correct 119 ms 18832 KB Output is correct
34 Correct 94 ms 18704 KB Output is correct
35 Correct 117 ms 18832 KB Output is correct
36 Correct 108 ms 18832 KB Output is correct
37 Correct 106 ms 18704 KB Output is correct
38 Correct 104 ms 18704 KB Output is correct
39 Correct 115 ms 18704 KB Output is correct
40 Correct 129 ms 18704 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 291 ms 6764 KB Output is correct
12 Correct 288 ms 6252 KB Output is correct
13 Correct 338 ms 5740 KB Output is correct
14 Correct 315 ms 5636 KB Output is correct
15 Correct 305 ms 6636 KB Output is correct
16 Correct 360 ms 5868 KB Output is correct
17 Correct 366 ms 5740 KB Output is correct
18 Correct 238 ms 7660 KB Output is correct
19 Correct 260 ms 4716 KB Output is correct
20 Correct 307 ms 6532 KB Output is correct
21 Correct 339 ms 7148 KB Output is correct
22 Correct 385 ms 7276 KB Output is correct
23 Correct 407 ms 6252 KB Output is correct
24 Correct 428 ms 6124 KB Output is correct
25 Correct 362 ms 8064 KB Output is correct
26 Correct 488 ms 6680 KB Output is correct
27 Correct 444 ms 6544 KB Output is correct
28 Correct 256 ms 9196 KB Output is correct
29 Correct 294 ms 4972 KB Output is correct
30 Correct 376 ms 7040 KB Output is correct
31 Correct 442 ms 7020 KB Output is correct
32 Correct 455 ms 6764 KB Output is correct
33 Correct 380 ms 5484 KB Output is correct
34 Correct 435 ms 5612 KB Output is correct
35 Correct 460 ms 6252 KB Output is correct
36 Correct 253 ms 4460 KB Output is correct
37 Correct 336 ms 6380 KB Output is correct
38 Correct 351 ms 4460 KB Output is correct
39 Correct 399 ms 5740 KB Output is correct
40 Correct 421 ms 5228 KB Output is correct
41 Correct 95 ms 19088 KB Output is correct
42 Correct 94 ms 18960 KB Output is correct
43 Correct 109 ms 18832 KB Output is correct
44 Correct 144 ms 18832 KB Output is correct
45 Correct 95 ms 18960 KB Output is correct
46 Correct 142 ms 18832 KB Output is correct
47 Correct 116 ms 18832 KB Output is correct
48 Correct 78 ms 18960 KB Output is correct
49 Correct 86 ms 18704 KB Output is correct
50 Correct 92 ms 18832 KB Output is correct
51 Correct 103 ms 18832 KB Output is correct
52 Correct 132 ms 18704 KB Output is correct
53 Correct 98 ms 18832 KB Output is correct
54 Correct 122 ms 18832 KB Output is correct
55 Correct 123 ms 18832 KB Output is correct
56 Correct 84 ms 18704 KB Output is correct
57 Correct 96 ms 18832 KB Output is correct
58 Correct 114 ms 18704 KB Output is correct
59 Correct 111 ms 18704 KB Output is correct
60 Correct 103 ms 18704 KB Output is correct
61 Correct 97 ms 18704 KB Output is correct
62 Correct 126 ms 18832 KB Output is correct
63 Correct 119 ms 18832 KB Output is correct
64 Correct 94 ms 18704 KB Output is correct
65 Correct 117 ms 18832 KB Output is correct
66 Correct 108 ms 18832 KB Output is correct
67 Correct 106 ms 18704 KB Output is correct
68 Correct 104 ms 18704 KB Output is correct
69 Correct 115 ms 18704 KB Output is correct
70 Correct 129 ms 18704 KB Output is correct
71 Correct 625 ms 23824 KB Output is correct
72 Correct 648 ms 24276 KB Output is correct
73 Correct 975 ms 22672 KB Output is correct
74 Correct 1439 ms 22960 KB Output is correct
75 Correct 594 ms 24592 KB Output is correct
76 Correct 1448 ms 23072 KB Output is correct
77 Correct 1085 ms 22672 KB Output is correct
78 Correct 355 ms 26640 KB Output is correct
79 Correct 491 ms 20752 KB Output is correct
80 Correct 644 ms 23824 KB Output is correct
81 Correct 882 ms 23744 KB Output is correct
82 Correct 1401 ms 22544 KB Output is correct
83 Correct 641 ms 21776 KB Output is correct
84 Correct 1235 ms 22416 KB Output is correct
85 Correct 1116 ms 22800 KB Output is correct
86 Correct 350 ms 20548 KB Output is correct
87 Correct 608 ms 23312 KB Output is correct
88 Correct 599 ms 20368 KB Output is correct
89 Correct 935 ms 22080 KB Output is correct
90 Correct 816 ms 22420 KB Output is correct
91 Correct 682 ms 21776 KB Output is correct
92 Correct 1287 ms 22672 KB Output is correct
93 Correct 1090 ms 22544 KB Output is correct
94 Correct 327 ms 20496 KB Output is correct
95 Correct 954 ms 22800 KB Output is correct
96 Correct 955 ms 22928 KB Output is correct
97 Correct 956 ms 22600 KB Output is correct
98 Correct 941 ms 22712 KB Output is correct
99 Correct 962 ms 22672 KB Output is correct
100 Correct 944 ms 22544 KB Output is correct