Submission #1191339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191339		epicci23	Snake Escaping (JOI18_snake_escaping)	C++20	0 / 100	0 ms	320 KiB

snake_escaping

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;


int pw[21], n, q;

string transform(int mask){
 string res = "";
 for(int i = n - 1; i >= 0; i--){
  if(mask >= 2 * pw[i]){
    res.push_back('?');
    mask -= 2 * pw[i];
  }
  else if(mask >= pw[i]){
    res.push_back('1');
    mask -= pw[i];
  }
  else res.push_back('0');
 } 
 
 reverse(all(res));

 return res;
}

int Shrink(string mask){
  int res = 0;
  for(int i = 0; i < n; i++){
    if(mask[i] == '?') res += pw[i] * 2;
    else if(mask[i] == '1') res += pw[i];
  }
  return res;
}


void _(){
  cin >> n >> q;


  pw[0] = 1;
  for(int i = 1; i < 21; i++) pw[i] = pw[i-1] * 3;

  string s;
  cin >> s;

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

  if(n <= 8){
    int dp[pw[n]];
    memset(dp,0,sizeof(dp));

    for(int i = 0; i < (1<<n); i++){
     int nw = 0;
     for(int j = 0; j < n; j++){
       if(i>>j&1) nw += pw[j];
     }
     dp[nw] = cost[i];
    }

    for(int i = 0; i < pw[n]; i++){
      string cur = transform(i); 

      for(int j = n - 1; j >= 0; j--){
        if(cur[j] == '?'){
          dp[i] = dp[i - pw[j]] + dp[i - 2 * pw[j]];
          break;
        }
      }

      //cout << i << " : " << dp[i] << '\n';
    }

    while(q--){
     string cur;
     cin >> cur;
     reverse(all(cur));
     int mask = Shrink(cur);
     cout << dp[mask] << '\n';
    }
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25