oj.uz

Submission #897560

# Submission time Handle Problem Language Result Execution time Memory
897560 2024-01-03T12:21:36 Z avighna Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 1859 ms 47416 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll N = 20;

ll dp[1 << N], dp2[1 << N];
ll cnt[256];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll l, q;
  cin >> l >> q;
  string s;
  cin >> s;

  for (ll i = 0; i < s.length(); ++i) {
    dp[i] = dp2[i] = s[i] - '0';
  }
  for (ll i = 0; i < N; ++i) {
    for (ll mask = 0; mask < (1 << N); ++mask) {
      if (mask & (1 << i)) {
        dp[mask] += dp[mask ^ (1 << i)];
      } else {
        dp2[mask] += dp2[mask ^ (1 << i)];
      }
    }
  }

  while (q--) {
    string t;
    cin >> t;
    ll ans = 0;
    cnt['1'] = cnt['0'] = cnt['?'] = 0;
    for (auto &i : t) {
      cnt[i]++;
    }
    if (cnt['?'] <= 6) {
      vector<ll> loc;
      ll val = 0;
      for (ll i = 0; i < t.length(); ++i) {
        if (t[i] == '?') {
          loc.push_back(t.length() - i - 1);
        }
        val += (1 << (t.length() - i - 1)) * (t[i] == '1');
      }
      queue<pair<ll, ll>> q;
      q.push({val, -1});
      for (ll i = 0; i < cnt['?']; ++i) {
        ll sz = q.size();
        while (sz--) {
          ll v = q.front().first;
          ll idx = q.front().second + 1;
          q.pop();
          q.push({v, idx});
          v ^= (1 << loc[idx]);
          q.push({v, idx});
        }
      }
      while (!q.empty()) {
        ll v = q.front().first;
        q.pop();
        ans += s[v] - '0';
      }
    } else if (cnt['1'] <= 6) {
      vector<ll> loc;
      ll val = 0;
      for (ll i = 0; i < t.length(); ++i) {
        if (t[i] == '1') {
          loc.push_back(t.length() - i - 1);
        }
        val += (1 << (t.length() - i - 1)) * (t[i] == '1' || t[i] == '?');
      }
      queue<pair<ll, ll>> q;
      q.push({val, -1});
      for (ll i = 0; i < cnt['1']; ++i) {
        ll sz = q.size();
        while (sz--) {
          ll v = q.front().first;
          ll idx = q.front().second + 1;
          q.pop();
          q.push({v, idx});
          v ^= (1 << loc[idx]);
          q.push({v, idx});
        }
      }
      while (!q.empty()) {
        ll v = q.front().first;
        q.pop();
        ans +=
            dp[v] *
            ((__builtin_popcount(v) - cnt['?']) % 2 == cnt['1'] % 2 ? 1 : -1);
      }
    } else {
      vector<ll> loc;
      ll val = 0;
      for (ll i = 0; i < t.length(); ++i) {
        if (t[i] == '0') {
          loc.push_back(t.length() - i - 1);
        }
        val += (1 << (t.length() - i - 1)) * (t[i] == '1');
      }
      queue<pair<ll, ll>> q;
      q.push({val, -1});
      for (ll i = 0; i < cnt['0']; ++i) {
        ll sz = q.size();
        while (sz--) {
          ll v = q.front().first;
          ll idx = q.front().second + 1;
          q.pop();
          q.push({v, idx});
          v ^= (1 << loc[idx]);
          q.push({v, idx});
        }
      }
      while (!q.empty()) {
        ll v = q.front().first;
        q.pop();
        ans += dp2[v] * ((__builtin_popcount(v) - cnt['1']) % 2 == 0 ? 1 : -1);
      }
    }
    cout << ans << "\n";
  }
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:21:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for (ll i = 0; i < s.length(); ++i) {
      |                  ~~^~~~~~~~~~~~
snake_escaping.cpp:40:11: warning: array subscript has type 'char' [-Wchar-subscripts]
   40 |       cnt[i]++;
      |           ^
snake_escaping.cpp:45:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |       for (ll i = 0; i < t.length(); ++i) {
      |                      ~~^~~~~~~~~~~~
snake_escaping.cpp:72:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |       for (ll i = 0; i < t.length(); ++i) {
      |                      ~~^~~~~~~~~~~~
snake_escaping.cpp:101:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |       for (ll i = 0; i < t.length(); ++i) {
      |                      ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16732 KB Output is correct
2 Correct 29 ms 16728 KB Output is correct
3 Correct 26 ms 16732 KB Output is correct
4 Correct 26 ms 16732 KB Output is correct
5 Correct 27 ms 16868 KB Output is correct
6 Correct 27 ms 16728 KB Output is correct
7 Correct 29 ms 16860 KB Output is correct
8 Correct 26 ms 16732 KB Output is correct
9 Correct 26 ms 16732 KB Output is correct
10 Correct 26 ms 16732 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16732 KB Output is correct
2 Correct 29 ms 16728 KB Output is correct
3 Correct 26 ms 16732 KB Output is correct
4 Correct 26 ms 16732 KB Output is correct
5 Correct 27 ms 16868 KB Output is correct
6 Correct 27 ms 16728 KB Output is correct
7 Correct 29 ms 16860 KB Output is correct
8 Correct 26 ms 16732 KB Output is correct
9 Correct 26 ms 16732 KB Output is correct
10 Correct 26 ms 16732 KB Output is correct
11 Correct 875 ms 29424 KB Output is correct
12 Correct 742 ms 29000 KB Output is correct
13 Correct 408 ms 27988 KB Output is correct
14 Correct 419 ms 28408 KB Output is correct
15 Correct 1430 ms 29332 KB Output is correct
16 Correct 577 ms 28496 KB Output is correct
17 Correct 538 ms 28632 KB Output is correct
18 Correct 232 ms 30200 KB Output is correct
19 Correct 193 ms 27220 KB Output is correct
20 Correct 789 ms 29048 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16732 KB Output is correct
2 Correct 29 ms 16728 KB Output is correct
3 Correct 26 ms 16732 KB Output is correct
4 Correct 26 ms 16732 KB Output is correct
5 Correct 27 ms 16868 KB Output is correct
6 Correct 27 ms 16728 KB Output is correct
7 Correct 29 ms 16860 KB Output is correct
8 Correct 26 ms 16732 KB Output is correct
9 Correct 26 ms 16732 KB Output is correct
10 Correct 26 ms 16732 KB Output is correct
11 Correct 875 ms 29424 KB Output is correct
12 Correct 742 ms 29000 KB Output is correct
13 Correct 408 ms 27988 KB Output is correct
14 Correct 419 ms 28408 KB Output is correct
15 Correct 1430 ms 29332 KB Output is correct
16 Correct 577 ms 28496 KB Output is correct
17 Correct 538 ms 28632 KB Output is correct
18 Correct 232 ms 30200 KB Output is correct
19 Correct 193 ms 27220 KB Output is correct
20 Correct 789 ms 29048 KB Output is correct
21 Correct 1695 ms 31620 KB Output is correct
22 Correct 679 ms 31704 KB Output is correct
23 Correct 628 ms 30580 KB Output is correct
24 Correct 618 ms 30484 KB Output is correct
25 Correct 463 ms 32604 KB Output is correct
26 Correct 774 ms 31048 KB Output is correct
27 Correct 727 ms 30860 KB Output is correct
28 Correct 250 ms 33544 KB Output is correct
29 Correct 239 ms 29420 KB Output is correct
30 Correct 1155 ms 31628 KB Output is correct
31 Correct 1493 ms 31500 KB Output is correct
32 Correct 928 ms 31480 KB Output is correct
33 Correct 417 ms 30508 KB Output is correct
34 Correct 583 ms 30636 KB Output is correct
35 Correct 706 ms 31004 KB Output is correct
36 Correct 218 ms 29524 KB Output is correct
37 Correct 1454 ms 31648 KB Output is correct
38 Correct 210 ms 29408 KB Output is correct
39 Correct 587 ms 30800 KB Output is correct
40 Correct 576 ms 30576 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16732 KB Output is correct
2 Correct 29 ms 16728 KB Output is correct
3 Correct 26 ms 16732 KB Output is correct
4 Correct 26 ms 16732 KB Output is correct
5 Correct 27 ms 16868 KB Output is correct
6 Correct 27 ms 16728 KB Output is correct
7 Correct 29 ms 16860 KB Output is correct
8 Correct 26 ms 16732 KB Output is correct
9 Correct 26 ms 16732 KB Output is correct
10 Correct 26 ms 16732 KB Output is correct
11 Correct 46 ms 20304 KB Output is correct
12 Correct 41 ms 20080 KB Output is correct
13 Correct 65 ms 20064 KB Output is correct
14 Correct 115 ms 20208 KB Output is correct
15 Correct 57 ms 20208 KB Output is correct
16 Correct 101 ms 20264 KB Output is correct
17 Correct 84 ms 20068 KB Output is correct
18 Correct 37 ms 20376 KB Output is correct
19 Correct 36 ms 19956 KB Output is correct
20 Correct 46 ms 20268 KB Output is correct
21 Correct 70 ms 20208 KB Output is correct
22 Correct 111 ms 20256 KB Output is correct
23 Correct 55 ms 20064 KB Output is correct
24 Correct 100 ms 20208 KB Output is correct
25 Correct 86 ms 20256 KB Output is correct
26 Correct 36 ms 19956 KB Output is correct
27 Correct 35 ms 20212 KB Output is correct
28 Correct 36 ms 19952 KB Output is correct
29 Correct 64 ms 20208 KB Output is correct
30 Correct 100 ms 20160 KB Output is correct
31 Correct 53 ms 20060 KB Output is correct
32 Correct 100 ms 20044 KB Output is correct
33 Correct 91 ms 20052 KB Output is correct
34 Correct 36 ms 19960 KB Output is correct
35 Correct 69 ms 20208 KB Output is correct
36 Correct 80 ms 20208 KB Output is correct
37 Correct 68 ms 20212 KB Output is correct
38 Correct 71 ms 20108 KB Output is correct
39 Correct 93 ms 20048 KB Output is correct
40 Correct 78 ms 20208 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16732 KB Output is correct
2 Correct 29 ms 16728 KB Output is correct
3 Correct 26 ms 16732 KB Output is correct
4 Correct 26 ms 16732 KB Output is correct
5 Correct 27 ms 16868 KB Output is correct
6 Correct 27 ms 16728 KB Output is correct
7 Correct 29 ms 16860 KB Output is correct
8 Correct 26 ms 16732 KB Output is correct
9 Correct 26 ms 16732 KB Output is correct
10 Correct 26 ms 16732 KB Output is correct
11 Correct 875 ms 29424 KB Output is correct
12 Correct 742 ms 29000 KB Output is correct
13 Correct 408 ms 27988 KB Output is correct
14 Correct 419 ms 28408 KB Output is correct
15 Correct 1430 ms 29332 KB Output is correct
16 Correct 577 ms 28496 KB Output is correct
17 Correct 538 ms 28632 KB Output is correct
18 Correct 232 ms 30200 KB Output is correct
19 Correct 193 ms 27220 KB Output is correct
20 Correct 789 ms 29048 KB Output is correct
21 Correct 1695 ms 31620 KB Output is correct
22 Correct 679 ms 31704 KB Output is correct
23 Correct 628 ms 30580 KB Output is correct
24 Correct 618 ms 30484 KB Output is correct
25 Correct 463 ms 32604 KB Output is correct
26 Correct 774 ms 31048 KB Output is correct
27 Correct 727 ms 30860 KB Output is correct
28 Correct 250 ms 33544 KB Output is correct
29 Correct 239 ms 29420 KB Output is correct
30 Correct 1155 ms 31628 KB Output is correct
31 Correct 1493 ms 31500 KB Output is correct
32 Correct 928 ms 31480 KB Output is correct
33 Correct 417 ms 30508 KB Output is correct
34 Correct 583 ms 30636 KB Output is correct
35 Correct 706 ms 31004 KB Output is correct
36 Correct 218 ms 29524 KB Output is correct
37 Correct 1454 ms 31648 KB Output is correct
38 Correct 210 ms 29408 KB Output is correct
39 Correct 587 ms 30800 KB Output is correct
40 Correct 576 ms 30576 KB Output is correct
41 Correct 46 ms 20304 KB Output is correct
42 Correct 41 ms 20080 KB Output is correct
43 Correct 65 ms 20064 KB Output is correct
44 Correct 115 ms 20208 KB Output is correct
45 Correct 57 ms 20208 KB Output is correct
46 Correct 101 ms 20264 KB Output is correct
47 Correct 84 ms 20068 KB Output is correct
48 Correct 37 ms 20376 KB Output is correct
49 Correct 36 ms 19956 KB Output is correct
50 Correct 46 ms 20268 KB Output is correct
51 Correct 70 ms 20208 KB Output is correct
52 Correct 111 ms 20256 KB Output is correct
53 Correct 55 ms 20064 KB Output is correct
54 Correct 100 ms 20208 KB Output is correct
55 Correct 86 ms 20256 KB Output is correct
56 Correct 36 ms 19956 KB Output is correct
57 Correct 35 ms 20212 KB Output is correct
58 Correct 36 ms 19952 KB Output is correct
59 Correct 64 ms 20208 KB Output is correct
60 Correct 100 ms 20160 KB Output is correct
61 Correct 53 ms 20060 KB Output is correct
62 Correct 100 ms 20044 KB Output is correct
63 Correct 91 ms 20052 KB Output is correct
64 Correct 36 ms 19960 KB Output is correct
65 Correct 69 ms 20208 KB Output is correct
66 Correct 80 ms 20208 KB Output is correct
67 Correct 68 ms 20212 KB Output is correct
68 Correct 71 ms 20108 KB Output is correct
69 Correct 93 ms 20048 KB Output is correct
70 Correct 78 ms 20208 KB Output is correct
71 Correct 292 ms 39820 KB Output is correct
72 Correct 369 ms 39664 KB Output is correct
73 Correct 872 ms 38188 KB Output is correct
74 Correct 1859 ms 39304 KB Output is correct
75 Correct 709 ms 45432 KB Output is correct
76 Correct 1565 ms 43752 KB Output is correct
77 Correct 1240 ms 43692 KB Output is correct
78 Correct 296 ms 47416 KB Output is correct
79 Correct 268 ms 41460 KB Output is correct
80 Correct 429 ms 44992 KB Output is correct
81 Correct 986 ms 44152 KB Output is correct
82 Correct 1797 ms 43496 KB Output is correct
83 Correct 667 ms 42704 KB Output is correct
84 Correct 1583 ms 43432 KB Output is correct
85 Correct 1240 ms 43760 KB Output is correct
86 Correct 265 ms 41456 KB Output is correct
87 Correct 284 ms 44384 KB Output is correct
88 Correct 260 ms 41460 KB Output is correct
89 Correct 864 ms 43224 KB Output is correct
90 Correct 1609 ms 43860 KB Output is correct
91 Correct 651 ms 42596 KB Output is correct
92 Correct 1617 ms 44048 KB Output is correct
93 Correct 1244 ms 43884 KB Output is correct
94 Correct 262 ms 41460 KB Output is correct
95 Correct 946 ms 43660 KB Output is correct
96 Correct 947 ms 43412 KB Output is correct
97 Correct 943 ms 43508 KB Output is correct
98 Correct 940 ms 43812 KB Output is correct
99 Correct 957 ms 43520 KB Output is correct
100 Correct 944 ms 43752 KB Output is correct