Submission #1191356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191356		epicci23	Snake Escaping (JOI18_snake_escaping)	C++20	22 / 100	2086 ms	18996 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 <= 13){
  	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;
        }
      }
    }

    while(q--){
     string cur;
     cin >> cur;
     reverse(all(cur));
     int mask = Shrink(cur);
     cout << dp[mask] << '\n';
    }
  }
  else{
  	vector<int> Ans(q, 0), Mask(q, 0), Mask1(q, 0), Mask2(q, 0);
    int dp[pw[n - 8]];

    int Nw[1<<(n-8)];
    memset(Nw,0,sizeof(Nw));

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

    for(int i = 0; i < q; i++){
      string s; cin >> s;
      reverse(all(s));

      for(int j = 0; j < n - 8; j++){
       if(s[j] == '1') Mask[i] += pw[j];
       else if(s[j] == '?') Mask[i] += 2 * pw[j];
      }

      for(int j = n - 8; j < n; j++){
        if(s[j] == '1'){
          Mask1[i] += (1 << j);
          Mask2[i] += (1 << j);
        }
        else if(s[j] == '?') Mask1[i] += (1 << j);
      }
    }

   	for(int lf = 0; lf < 256; lf++){ // son 8 biti fixle
      memset(dp,0,sizeof(dp));

      int left = 0;
      for(int i = n - 8; i < n; i++) if(lf>>i&1) left += (1<<i);

      for(int i = 0; i < (1 << (n - 8)); i++) dp[Nw[i]] = cost[i + left];
      
      for(int i = 0; i < pw[n - 8]; i++){
       string cur = transform(i); 

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

      for(int i = 0; i < q; i++){
        int val1 = (Mask1[i] ^ left);
        int val2 = (Mask2[i] ^ left);

        if(val1 & val2) continue;

        Ans[i] += dp[Mask[i]];
      }
    }

  	for(int i = 0; i < q; i++) cout << Ans[i] << '\n';
  }
}

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

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