Submission #1191379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191379		epicci23	Snake Escaping (JOI18_snake_escaping)	C++20	22 / 100	357 ms	18936 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 - 7]], Nw[1<<(n-7)], Transition[pw[n - 7]];
    memset(Transition, -1, sizeof(Transition));

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

       for(int j = n - 8; j >= 0; j--){
         if(cur[j] == '?'){
          Transition[i] = j;
          break;
        }
       }
    }

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

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

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

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

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

      int left = 0;
      for(int i = n - 7; i < n; i++){
      	int hm = i - (n - 7);
      	if(lf>>hm&1) left += (1<<i);
      }

      for(int i = 0; i < (1 << (n - 7)); i++) dp[Nw[i]] = cost[i + left];
      
      for(int i = 0; i < pw[n - 7]; i++){
        if(Transition[i] == -1) continue; 
        int j = Transition[i];
        dp[i] = dp[i - pw[j]] + dp[i - 2 * pw[j]];
      }

      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