oj.uz

Submission #1007735

# Submission time Handle Problem Language Result Execution time Memory
1007735 2024-06-25T12:00:40 Z ihne Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 1041 ms 54868 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
const int mn=1e5+5;
const int mod=1e9+7;
int dp[1100000][2];
int a[1100000];
signed main(){
  //freopen("","r",stdin);
  //freopen("","w",stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int l,q;
  cin>>l>>q;
  for (int i=0;i<(1<<l);i++){
    char c;
    cin>>c;
    dp[i][0]=c-'0';
    dp[i][1]=c-'0';
    a[i]=c-'0';
  }
  for (int i=0;i<l;i++){
    for (int mask=0;mask<(1<<l);mask++){
      if (mask>>i&1){
        dp[mask][0]+=dp[mask^(1<<i)][0];
      }
    }
  }
  for (int i=0;i<l;i++){
    for (int mask=(1<<l)-1;mask;mask--){
      if (mask>>i&1){
        dp[mask^(1<<i)][1]+=dp[mask][1];
      }
    }
  }
  while (q--){
    string s;
    cin>>s;
    vector<int> pos,p0,p1;
    int c0=0,c1=0,c2=0;
    int m=0;
    for (int i=0;i<l;i++){
      if (s[i]=='0') {
        c0++;
        p0.pb(i);
      }
      else if (s[i]=='1'){
        c1++;
        m^=(1<<(l-i-1));
        p1.pb(i);
      }
      else {
        c2++;
        pos.pb(i);
      }
    }
    int ans=0;
    if (c0<=6){
      for (int mask=0;mask<(1<<c0);mask++){
        int msk=m;
        int cnt=0;
        for (int i=0;i<c0;i++){
          if (mask>>i&1) {
            msk^=(1<<(l-p0[i]-1));
          }
          else cnt++;
        }
        if ((cnt&1)==(c0&1))ans+=dp[msk][1];
        else ans-=dp[msk][1];
      }
    }
    else if (c1<=6){
      for (int i=0;i<c2;i++){
        m^=(1<<(l-pos[i]-1));
      }
      for (int mask=0;mask<(1<<c1);mask++){
        int msk=m;
        int cnt=0;
        for (int i=0;i<c1;i++){
          if (mask>>i&1) cnt++;
          else{
            msk^=(1<<(l-p1[i]-1));
          }
        }
        if ((cnt&1)==(c1&1))ans+=dp[msk][0];
        else ans-=dp[msk][0];
      }
    }
    else{
      for (int mask=0;mask<(1<<c2);mask++){
        int msk=m;
        for (int i=0;i<c2;i++){
          if (mask>>i&1) msk+=(1<<(l-pos[i]-1));
        }
        ans+=a[msk];
      }
    }
    cout<<ans<<"\n";
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2520 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 2408 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 2396 KB Output is correct
2 Correct 1 ms 2520 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 2408 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 293 ms 17236 KB Output is correct
12 Correct 447 ms 16720 KB Output is correct
13 Correct 445 ms 16208 KB Output is correct
14 Correct 335 ms 16196 KB Output is correct
15 Correct 310 ms 17168 KB Output is correct
16 Correct 329 ms 16416 KB Output is correct
17 Correct 399 ms 16212 KB Output is correct
18 Correct 188 ms 18156 KB Output is correct
19 Correct 399 ms 15184 KB Output is correct
20 Correct 278 ms 16724 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2520 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 2408 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 293 ms 17236 KB Output is correct
12 Correct 447 ms 16720 KB Output is correct
13 Correct 445 ms 16208 KB Output is correct
14 Correct 335 ms 16196 KB Output is correct
15 Correct 310 ms 17168 KB Output is correct
16 Correct 329 ms 16416 KB Output is correct
17 Correct 399 ms 16212 KB Output is correct
18 Correct 188 ms 18156 KB Output is correct
19 Correct 399 ms 15184 KB Output is correct
20 Correct 278 ms 16724 KB Output is correct
21 Correct 302 ms 20044 KB Output is correct
22 Correct 456 ms 20304 KB Output is correct
23 Correct 734 ms 19320 KB Output is correct
24 Correct 494 ms 19056 KB Output is correct
25 Correct 353 ms 21076 KB Output is correct
26 Correct 467 ms 19792 KB Output is correct
27 Correct 534 ms 19632 KB Output is correct
28 Correct 191 ms 22216 KB Output is correct
29 Correct 635 ms 18256 KB Output is correct
30 Correct 326 ms 20300 KB Output is correct
31 Correct 476 ms 20304 KB Output is correct
32 Correct 429 ms 20096 KB Output is correct
33 Correct 343 ms 19028 KB Output is correct
34 Correct 529 ms 19160 KB Output is correct
35 Correct 524 ms 19680 KB Output is correct
36 Correct 182 ms 18260 KB Output is correct
37 Correct 285 ms 20044 KB Output is correct
38 Correct 600 ms 18256 KB Output is correct
39 Correct 462 ms 19348 KB Output is correct
40 Correct 401 ms 19220 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2520 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 2408 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 67 ms 27732 KB Output is correct
12 Correct 68 ms 27688 KB Output is correct
13 Correct 82 ms 27520 KB Output is correct
14 Correct 96 ms 27476 KB Output is correct
15 Correct 76 ms 27732 KB Output is correct
16 Correct 97 ms 27736 KB Output is correct
17 Correct 95 ms 27520 KB Output is correct
18 Correct 59 ms 27728 KB Output is correct
19 Correct 65 ms 27532 KB Output is correct
20 Correct 67 ms 27728 KB Output is correct
21 Correct 83 ms 27732 KB Output is correct
22 Correct 97 ms 27512 KB Output is correct
23 Correct 79 ms 27512 KB Output is correct
24 Correct 99 ms 27596 KB Output is correct
25 Correct 104 ms 27732 KB Output is correct
26 Correct 57 ms 27516 KB Output is correct
27 Correct 71 ms 27728 KB Output is correct
28 Correct 71 ms 27528 KB Output is correct
29 Correct 82 ms 27476 KB Output is correct
30 Correct 124 ms 27500 KB Output is correct
31 Correct 74 ms 27476 KB Output is correct
32 Correct 104 ms 27728 KB Output is correct
33 Correct 93 ms 27732 KB Output is correct
34 Correct 57 ms 27476 KB Output is correct
35 Correct 91 ms 27732 KB Output is correct
36 Correct 85 ms 27728 KB Output is correct
37 Correct 89 ms 27732 KB Output is correct
38 Correct 84 ms 27512 KB Output is correct
39 Correct 83 ms 27476 KB Output is correct
40 Correct 77 ms 27728 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2520 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 2408 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 293 ms 17236 KB Output is correct
12 Correct 447 ms 16720 KB Output is correct
13 Correct 445 ms 16208 KB Output is correct
14 Correct 335 ms 16196 KB Output is correct
15 Correct 310 ms 17168 KB Output is correct
16 Correct 329 ms 16416 KB Output is correct
17 Correct 399 ms 16212 KB Output is correct
18 Correct 188 ms 18156 KB Output is correct
19 Correct 399 ms 15184 KB Output is correct
20 Correct 278 ms 16724 KB Output is correct
21 Correct 302 ms 20044 KB Output is correct
22 Correct 456 ms 20304 KB Output is correct
23 Correct 734 ms 19320 KB Output is correct
24 Correct 494 ms 19056 KB Output is correct
25 Correct 353 ms 21076 KB Output is correct
26 Correct 467 ms 19792 KB Output is correct
27 Correct 534 ms 19632 KB Output is correct
28 Correct 191 ms 22216 KB Output is correct
29 Correct 635 ms 18256 KB Output is correct
30 Correct 326 ms 20300 KB Output is correct
31 Correct 476 ms 20304 KB Output is correct
32 Correct 429 ms 20096 KB Output is correct
33 Correct 343 ms 19028 KB Output is correct
34 Correct 529 ms 19160 KB Output is correct
35 Correct 524 ms 19680 KB Output is correct
36 Correct 182 ms 18260 KB Output is correct
37 Correct 285 ms 20044 KB Output is correct
38 Correct 600 ms 18256 KB Output is correct
39 Correct 462 ms 19348 KB Output is correct
40 Correct 401 ms 19220 KB Output is correct
41 Correct 67 ms 27732 KB Output is correct
42 Correct 68 ms 27688 KB Output is correct
43 Correct 82 ms 27520 KB Output is correct
44 Correct 96 ms 27476 KB Output is correct
45 Correct 76 ms 27732 KB Output is correct
46 Correct 97 ms 27736 KB Output is correct
47 Correct 95 ms 27520 KB Output is correct
48 Correct 59 ms 27728 KB Output is correct
49 Correct 65 ms 27532 KB Output is correct
50 Correct 67 ms 27728 KB Output is correct
51 Correct 83 ms 27732 KB Output is correct
52 Correct 97 ms 27512 KB Output is correct
53 Correct 79 ms 27512 KB Output is correct
54 Correct 99 ms 27596 KB Output is correct
55 Correct 104 ms 27732 KB Output is correct
56 Correct 57 ms 27516 KB Output is correct
57 Correct 71 ms 27728 KB Output is correct
58 Correct 71 ms 27528 KB Output is correct
59 Correct 82 ms 27476 KB Output is correct
60 Correct 124 ms 27500 KB Output is correct
61 Correct 74 ms 27476 KB Output is correct
62 Correct 104 ms 27728 KB Output is correct
63 Correct 93 ms 27732 KB Output is correct
64 Correct 57 ms 27476 KB Output is correct
65 Correct 91 ms 27732 KB Output is correct
66 Correct 85 ms 27728 KB Output is correct
67 Correct 89 ms 27732 KB Output is correct
68 Correct 84 ms 27512 KB Output is correct
69 Correct 83 ms 27476 KB Output is correct
70 Correct 77 ms 27728 KB Output is correct
71 Correct 485 ms 52048 KB Output is correct
72 Correct 508 ms 52064 KB Output is correct
73 Correct 831 ms 50512 KB Output is correct
74 Correct 1041 ms 51012 KB Output is correct
75 Correct 576 ms 53076 KB Output is correct
76 Correct 1010 ms 51284 KB Output is correct
77 Correct 931 ms 51056 KB Output is correct
78 Correct 292 ms 54868 KB Output is correct
79 Correct 465 ms 48980 KB Output is correct
80 Correct 482 ms 51968 KB Output is correct
81 Correct 756 ms 52056 KB Output is correct
82 Correct 970 ms 51048 KB Output is correct
83 Correct 560 ms 50296 KB Output is correct
84 Correct 970 ms 50836 KB Output is correct
85 Correct 905 ms 51176 KB Output is correct
86 Correct 293 ms 49040 KB Output is correct
87 Correct 438 ms 52048 KB Output is correct
88 Correct 504 ms 48976 KB Output is correct
89 Correct 803 ms 50508 KB Output is correct
90 Correct 987 ms 50904 KB Output is correct
91 Correct 604 ms 50000 KB Output is correct
92 Correct 1034 ms 51372 KB Output is correct
93 Correct 978 ms 51132 KB Output is correct
94 Correct 267 ms 48980 KB Output is correct
95 Correct 754 ms 51056 KB Output is correct
96 Correct 764 ms 50976 KB Output is correct
97 Correct 782 ms 51132 KB Output is correct
98 Correct 732 ms 50964 KB Output is correct
99 Correct 787 ms 51068 KB Output is correct
100 Correct 801 ms 51028 KB Output is correct