oj.uz

Submission #1099068

# Submission time Handle Problem Language Result Execution time Memory
1099068 2024-10-10T13:05:03 Z trie Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 342 ms 20052 KB 
#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define ii pair<int, int>
#define iii pair<ii, int>
#define ll long long
#define pb push_back
#define pli pair<ll, int>
#define all(v) (v).begin(), (v).end()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define cntbit(mask) __builtin_popcount(mask)
#define getbit(x, i) ((x >> i) & 1)
#define MASK(i) (1 << i)
#define pli pair<ll, int>
using namespace std;

template<class T1, class T2>
bool maximize(T1 &a, T2 b){if(a < b){a = b; return 1;} return 0;}

template<class T1, class T2>
bool minimize(T1 &a, T2 b){if(a > b){a = b; return 1;} return 0;}

const int N = 1e5 + 5;
const int V = 1e6 + 5;
const int MOD = 1e9 + 7;

int n, q, cost[MASK(20) + 5], f[MASK(20) + 5];
string s;

void solve() {
	cin >> n >> q;
	cin >> s;

	for(int i = 0 ; i < (1 << n) ; i++) f[i] = cost[i] = (s[i] - '0');

	for(int i = 0 ; i < n ; i++)
		for(int mask = 0 ; mask < MASK(n) ; mask++)
			if (getbit(mask, i)) cost[mask] += cost[mask ^ MASK(i)];

    for(int i = 0 ; i < n ; i++)
        for(int mask = 0 ; mask < MASK(n) ; mask++)
            if (!getbit(mask, i)) f[mask] += f[mask | MASK(i)];

	for(int i = 0 ; i < q ; i++) {
		string t;	cin >> t;
		int mask1, mask2, mask3, sz = (int) t.size() - 1;
		ll ans;
		mask1 = mask2 = mask3 = ans = 0;

		for(int i = sz ; i >= 0 ; i--)
			if (t[i] == '1') mask1 |= MASK(sz - i);
			else if (t[i] == '?') mask2 |= MASK(sz - i);
            else mask3 |= MASK(sz - i);

        if (cntbit(mask1) <= 6) {
            int c = cntbit(mask1) & 1;
            for(int submask = mask1 ; submask >= 0 ; submask = (submask - 1) & mask1) {
                if ((cntbit(submask) & 1) == c) ans += cost[submask + mask2];
                else ans -= cost[submask + mask2];
                if (submask == 0) break;
            }
        } else if (cntbit(mask2) <= 6) {
            for(int submask = mask2 ; submask >= 0 ; submask = (submask - 1) & mask2) {
                ans += (s[submask + mask1] - '0');
                if (submask == 0) break;
            }
        } else {
            int c = cntbit(mask3) & 1;
            for(int submask = mask3 ; submask >= 0 ; submask = (submask - 1) & mask3) {
                if ((cntbit(submask) & 1) == c) ans -= f[submask + mask1];
                else ans += f[submask + mask1];
                if (submask == 0) break;
            }
        }

		cout << ans << '\n';
	}
}

int main(void) {
    //freopen("task.inp", "r", stdin);
    //freopen("task.out", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
    int t = 1; while(t--) solve();
    return 0;
}

Compilation message

snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:41:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   41 |     for(int i = 0 ; i < n ; i++)
      |     ^~~
snake_escaping.cpp:45:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   45 |  for(int i = 0 ; i < q ; i++) {
      |  ^~~
snake_escaping.cpp:52:38: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   52 |    if (t[i] == '1') mask1 |= MASK(sz - i);
      |                                   ~~~^~~
snake_escaping.cpp:14:23: note: in definition of macro 'MASK'
   14 | #define MASK(i) (1 << i)
      |                       ^
snake_escaping.cpp:53:43: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   53 |    else if (t[i] == '?') mask2 |= MASK(sz - i);
      |                                        ~~~^~~
snake_escaping.cpp:14:23: note: in definition of macro 'MASK'
   14 | #define MASK(i) (1 << i)
      |                       ^
snake_escaping.cpp:54:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   54 |             else mask3 |= MASK(sz - i);
      |                                ~~~^~~
snake_escaping.cpp:14:23: note: in definition of macro 'MASK'
   14 | #define MASK(i) (1 << i)
      |                       ^

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 222 ms 15188 KB Output is correct
12 Correct 144 ms 14676 KB Output is correct
13 Correct 177 ms 14120 KB Output is correct
14 Correct 159 ms 14160 KB Output is correct
15 Correct 161 ms 15192 KB Output is correct
16 Correct 214 ms 14160 KB Output is correct
17 Correct 210 ms 14360 KB Output is correct
18 Correct 125 ms 16208 KB Output is correct
19 Correct 209 ms 13100 KB Output is correct
20 Correct 205 ms 14680 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 222 ms 15188 KB Output is correct
12 Correct 144 ms 14676 KB Output is correct
13 Correct 177 ms 14120 KB Output is correct
14 Correct 159 ms 14160 KB Output is correct
15 Correct 161 ms 15192 KB Output is correct
16 Correct 214 ms 14160 KB Output is correct
17 Correct 210 ms 14360 KB Output is correct
18 Correct 125 ms 16208 KB Output is correct
19 Correct 209 ms 13100 KB Output is correct
20 Correct 205 ms 14680 KB Output is correct
21 Correct 321 ms 18324 KB Output is correct
22 Correct 165 ms 18256 KB Output is correct
23 Correct 212 ms 17236 KB Output is correct
24 Correct 228 ms 17232 KB Output is correct
25 Correct 188 ms 19028 KB Output is correct
26 Correct 261 ms 17652 KB Output is correct
27 Correct 254 ms 17492 KB Output is correct
28 Correct 128 ms 20052 KB Output is correct
29 Correct 157 ms 16208 KB Output is correct
30 Correct 252 ms 18284 KB Output is correct
31 Correct 226 ms 18124 KB Output is correct
32 Correct 225 ms 18004 KB Output is correct
33 Correct 179 ms 17036 KB Output is correct
34 Correct 266 ms 17112 KB Output is correct
35 Correct 258 ms 17492 KB Output is correct
36 Correct 117 ms 16348 KB Output is correct
37 Correct 168 ms 18004 KB Output is correct
38 Correct 225 ms 16212 KB Output is correct
39 Correct 342 ms 17232 KB Output is correct
40 Correct 258 ms 17232 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Incorrect 45 ms 12016 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 222 ms 15188 KB Output is correct
12 Correct 144 ms 14676 KB Output is correct
13 Correct 177 ms 14120 KB Output is correct
14 Correct 159 ms 14160 KB Output is correct
15 Correct 161 ms 15192 KB Output is correct
16 Correct 214 ms 14160 KB Output is correct
17 Correct 210 ms 14360 KB Output is correct
18 Correct 125 ms 16208 KB Output is correct
19 Correct 209 ms 13100 KB Output is correct
20 Correct 205 ms 14680 KB Output is correct
21 Correct 321 ms 18324 KB Output is correct
22 Correct 165 ms 18256 KB Output is correct
23 Correct 212 ms 17236 KB Output is correct
24 Correct 228 ms 17232 KB Output is correct
25 Correct 188 ms 19028 KB Output is correct
26 Correct 261 ms 17652 KB Output is correct
27 Correct 254 ms 17492 KB Output is correct
28 Correct 128 ms 20052 KB Output is correct
29 Correct 157 ms 16208 KB Output is correct
30 Correct 252 ms 18284 KB Output is correct
31 Correct 226 ms 18124 KB Output is correct
32 Correct 225 ms 18004 KB Output is correct
33 Correct 179 ms 17036 KB Output is correct
34 Correct 266 ms 17112 KB Output is correct
35 Correct 258 ms 17492 KB Output is correct
36 Correct 117 ms 16348 KB Output is correct
37 Correct 168 ms 18004 KB Output is correct
38 Correct 225 ms 16212 KB Output is correct
39 Correct 342 ms 17232 KB Output is correct
40 Correct 258 ms 17232 KB Output is correct
41 Incorrect 45 ms 12016 KB Output isn't correct
42 Halted 0 ms 0 KB -