oj.uz

Submission #817283

# Submission time Handle Problem Language Result Execution time Memory
817283 2023-08-09T11:19:36 Z kwongweng Snake Escaping (JOI18_snake_escaping) C++17
75 / 100
 2000 ms 19984 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ll, int> li;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second

int main(){
  ios::sync_with_stdio(false);
  int L, Q; cin>>L>>Q;
  string s; cin >> s;
  int dp[1<<L]; FOR(i,0,(1<<L)) dp[i]=s[i]-'0';
  FOR(i,0,L){
    FOR(mask,0,(1<<L)){
      if (mask & (1<<i)) dp[mask] += dp[mask-(1<<i)];
    }
  }
  FOR(i,0,Q){
    string t; cin >> t; reverse(t.begin(), t.end());
    int cnt1=0, cnt2=0; FOR(j,0,L) {cnt1 += (t[j]=='?'); cnt2 += (t[j]=='1');}
    if (cnt1 <= cnt2){
      int ans = 0;
      vi a; int cur = 0;
      FOR(j,0,L){
        if (t[j]=='?') a.pb(j);
        else cur += (1<<j)*(t[j]-'0');
      }
      FOR(j,0,(1<<cnt1)){
        int val=0; FOR(k,0,cnt1){
          if (j & (1<<k)) val += (1<<a[k]);
        }
        //cout<<cur+val<<" ";
        ans+=s[cur+val]-'0';
      }
      cout<<ans<<'\n';
    }else{
      vi a; int cur=0;
      FOR(j,0,L){
        if (t[j]=='1') {a.pb(j); cur += (1<<j);}
        if (t[j]=='?') cur += (1<<j);
      }
      int ans = 0;
      FOR(j,0,(1<<cnt2)){
        int val=0; int num=0; FOR(k,0,cnt2){
          if (j & (1<<k)) {val += (1<<a[k]); num++;}
        }
        if (num % 2 == 0) ans += dp[cur-val];
        else ans -= dp[cur-val];
      }
      cout<<ans<<'\n';
    }
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 324 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 324 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 212 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 324 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 324 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 1483 ms 14988 KB Output is correct
12 Correct 1188 ms 14804 KB Output is correct
13 Correct 1268 ms 13940 KB Output is correct
14 Correct 1284 ms 14080 KB Output is correct
15 Correct 1310 ms 15104 KB Output is correct
16 Correct 1292 ms 14340 KB Output is correct
17 Correct 1371 ms 14180 KB Output is correct
18 Correct 1181 ms 16032 KB Output is correct
19 Correct 1162 ms 13120 KB Output is correct
20 Correct 1364 ms 14764 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 324 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 324 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 1483 ms 14988 KB Output is correct
12 Correct 1188 ms 14804 KB Output is correct
13 Correct 1268 ms 13940 KB Output is correct
14 Correct 1284 ms 14080 KB Output is correct
15 Correct 1310 ms 15104 KB Output is correct
16 Correct 1292 ms 14340 KB Output is correct
17 Correct 1371 ms 14180 KB Output is correct
18 Correct 1181 ms 16032 KB Output is correct
19 Correct 1162 ms 13120 KB Output is correct
20 Correct 1364 ms 14764 KB Output is correct
21 Correct 1906 ms 18152 KB Output is correct
22 Correct 1227 ms 18120 KB Output is correct
23 Correct 1327 ms 17272 KB Output is correct
24 Correct 1356 ms 17036 KB Output is correct
25 Correct 1378 ms 19168 KB Output is correct
26 Correct 1393 ms 17628 KB Output is correct
27 Correct 1425 ms 17452 KB Output is correct
28 Correct 1209 ms 19984 KB Output is correct
29 Correct 1206 ms 16008 KB Output is correct
30 Correct 1746 ms 18184 KB Output is correct
31 Correct 1462 ms 18164 KB Output is correct
32 Correct 1430 ms 18072 KB Output is correct
33 Correct 1306 ms 16868 KB Output is correct
34 Correct 1366 ms 17036 KB Output is correct
35 Correct 1389 ms 17448 KB Output is correct
36 Correct 1147 ms 16156 KB Output is correct
37 Correct 1236 ms 17960 KB Output is correct
38 Correct 1150 ms 16044 KB Output is correct
39 Correct 1426 ms 17136 KB Output is correct
40 Correct 1356 ms 17180 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 324 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 324 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 1898 ms 7772 KB Output is correct
12 Correct 90 ms 7788 KB Output is correct
13 Correct 103 ms 7788 KB Output is correct
14 Correct 122 ms 7756 KB Output is correct
15 Correct 96 ms 7820 KB Output is correct
16 Correct 120 ms 7776 KB Output is correct
17 Correct 128 ms 7736 KB Output is correct
18 Correct 85 ms 7896 KB Output is correct
19 Correct 90 ms 7676 KB Output is correct
20 Correct 994 ms 7844 KB Output is correct
21 Correct 147 ms 7784 KB Output is correct
22 Correct 158 ms 7968 KB Output is correct
23 Correct 123 ms 7764 KB Output is correct
24 Correct 133 ms 7796 KB Output is correct
25 Correct 136 ms 7800 KB Output is correct
26 Correct 82 ms 7608 KB Output is correct
27 Correct 92 ms 7788 KB Output is correct
28 Correct 99 ms 7600 KB Output is correct
29 Correct 129 ms 7780 KB Output is correct
30 Correct 116 ms 7748 KB Output is correct
31 Correct 99 ms 7864 KB Output is correct
32 Correct 120 ms 7812 KB Output is correct
33 Correct 147 ms 7744 KB Output is correct
34 Correct 88 ms 7716 KB Output is correct
35 Correct 257 ms 7928 KB Output is correct
36 Correct 243 ms 7788 KB Output is correct
37 Correct 241 ms 7828 KB Output is correct
38 Correct 245 ms 7748 KB Output is correct
39 Correct 243 ms 7744 KB Output is correct
40 Correct 251 ms 7908 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 324 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 324 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 1483 ms 14988 KB Output is correct
12 Correct 1188 ms 14804 KB Output is correct
13 Correct 1268 ms 13940 KB Output is correct
14 Correct 1284 ms 14080 KB Output is correct
15 Correct 1310 ms 15104 KB Output is correct
16 Correct 1292 ms 14340 KB Output is correct
17 Correct 1371 ms 14180 KB Output is correct
18 Correct 1181 ms 16032 KB Output is correct
19 Correct 1162 ms 13120 KB Output is correct
20 Correct 1364 ms 14764 KB Output is correct
21 Correct 1906 ms 18152 KB Output is correct
22 Correct 1227 ms 18120 KB Output is correct
23 Correct 1327 ms 17272 KB Output is correct
24 Correct 1356 ms 17036 KB Output is correct
25 Correct 1378 ms 19168 KB Output is correct
26 Correct 1393 ms 17628 KB Output is correct
27 Correct 1425 ms 17452 KB Output is correct
28 Correct 1209 ms 19984 KB Output is correct
29 Correct 1206 ms 16008 KB Output is correct
30 Correct 1746 ms 18184 KB Output is correct
31 Correct 1462 ms 18164 KB Output is correct
32 Correct 1430 ms 18072 KB Output is correct
33 Correct 1306 ms 16868 KB Output is correct
34 Correct 1366 ms 17036 KB Output is correct
35 Correct 1389 ms 17448 KB Output is correct
36 Correct 1147 ms 16156 KB Output is correct
37 Correct 1236 ms 17960 KB Output is correct
38 Correct 1150 ms 16044 KB Output is correct
39 Correct 1426 ms 17136 KB Output is correct
40 Correct 1356 ms 17180 KB Output is correct
41 Correct 1898 ms 7772 KB Output is correct
42 Correct 90 ms 7788 KB Output is correct
43 Correct 103 ms 7788 KB Output is correct
44 Correct 122 ms 7756 KB Output is correct
45 Correct 96 ms 7820 KB Output is correct
46 Correct 120 ms 7776 KB Output is correct
47 Correct 128 ms 7736 KB Output is correct
48 Correct 85 ms 7896 KB Output is correct
49 Correct 90 ms 7676 KB Output is correct
50 Correct 994 ms 7844 KB Output is correct
51 Correct 147 ms 7784 KB Output is correct
52 Correct 158 ms 7968 KB Output is correct
53 Correct 123 ms 7764 KB Output is correct
54 Correct 133 ms 7796 KB Output is correct
55 Correct 136 ms 7800 KB Output is correct
56 Correct 82 ms 7608 KB Output is correct
57 Correct 92 ms 7788 KB Output is correct
58 Correct 99 ms 7600 KB Output is correct
59 Correct 129 ms 7780 KB Output is correct
60 Correct 116 ms 7748 KB Output is correct
61 Correct 99 ms 7864 KB Output is correct
62 Correct 120 ms 7812 KB Output is correct
63 Correct 147 ms 7744 KB Output is correct
64 Correct 88 ms 7716 KB Output is correct
65 Correct 257 ms 7928 KB Output is correct
66 Correct 243 ms 7788 KB Output is correct
67 Correct 241 ms 7828 KB Output is correct
68 Correct 245 ms 7748 KB Output is correct
69 Correct 243 ms 7744 KB Output is correct
70 Correct 251 ms 7908 KB Output is correct
71 Execution timed out 2073 ms 8204 KB Time limit exceeded
72 Halted 0 ms 0 KB -