oj.uz

Submission #817012

# Submission time Handle Problem Language Result Execution time Memory
817012 2023-08-09T08:28:25 Z kwongweng Snake Escaping (JOI18_snake_escaping) C++17
5 / 100
 2000 ms 15020 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 cnt=0; FOR(j,0,L) cnt += (t[j]=='?');
    if (cnt <= 20){
      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<<cnt)){
        int val=0; FOR(k,0,cnt){
          if (j & (1<<k)) val += (1<<a[k]);
        }
        //cout<<cur+val<<" ";
        ans+=s[cur+val]-'0';
      }
      cout<<ans<<'\n';
    }
  }
  // x & y = 0 => bits of y = subset of bits of (1<<20)-1-x
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 324 KB Output is correct
2 Correct 3 ms 212 KB Output is correct
3 Correct 2 ms 212 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 212 KB Output is correct
7 Correct 3 ms 324 KB Output is correct
8 Correct 42 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 3 ms 212 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 324 KB Output is correct
2 Correct 3 ms 212 KB Output is correct
3 Correct 2 ms 212 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 212 KB Output is correct
7 Correct 3 ms 324 KB Output is correct
8 Correct 42 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 3 ms 212 KB Output is correct
11 Correct 1561 ms 15020 KB Output is correct
12 Execution timed out 2011 ms 14656 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 324 KB Output is correct
2 Correct 3 ms 212 KB Output is correct
3 Correct 2 ms 212 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 212 KB Output is correct
7 Correct 3 ms 324 KB Output is correct
8 Correct 42 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 3 ms 212 KB Output is correct
11 Correct 1561 ms 15020 KB Output is correct
12 Execution timed out 2011 ms 14656 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 324 KB Output is correct
2 Correct 3 ms 212 KB Output is correct
3 Correct 2 ms 212 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 212 KB Output is correct
7 Correct 3 ms 324 KB Output is correct
8 Correct 42 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 3 ms 212 KB Output is correct
11 Correct 1977 ms 8008 KB Output is correct
12 Execution timed out 2077 ms 7132 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 324 KB Output is correct
2 Correct 3 ms 212 KB Output is correct
3 Correct 2 ms 212 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 212 KB Output is correct
7 Correct 3 ms 324 KB Output is correct
8 Correct 42 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 3 ms 212 KB Output is correct
11 Correct 1561 ms 15020 KB Output is correct
12 Execution timed out 2011 ms 14656 KB Time limit exceeded
13 Halted 0 ms 0 KB -