Submission #1113368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113368		emad234	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	926 ms	48360 KiB

snake_escaping

#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<ll,int>
const int mxN = (1 << 20) + 5;
const int mod = 1e9 + 7;
using namespace std;
int sos[mxN][2][2];
signed main(){
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
  int n,q;
  cin >>n>>q;
  string s;
  cin>>s;
  for(int i = 0;i < n;i++){
    for(int mask = 0;mask < (1 << n);mask++){
      if(!i){
        sos[mask][0][0] = s[mask] - '0';
        if((mask &1)) sos[mask][0][0] += s[mask - 1] - '0';
        sos[mask][0][1] = s[mask] - '0';
        if((mask &1) == 0) sos[mask][0][1] += s[mask + 1] - '0';
        continue;
      }
      sos[mask][i &1][0] = sos[mask][(i - 1)&1][0];
      sos[mask][i &1][1] = sos[mask][(i - 1)&1][1];
      if(mask >> i & 1) sos[mask][(i)&1][0] += sos[mask - (1 << i)][(i - 1)&1][0];
      else sos[mask][i &1][1] += sos[mask + (1 << i)][(i - 1)&1][1];
    }
  }
  while(q--){
    string a;
    cin >>a;
    reverse(a.begin(),a.end());
    int Qcnt = 0, Ocnt = 0, Icnt = 0;
    for(auto x : a){
      if(x == '?') Qcnt++;
      else if(x == '1') Icnt++;
      else Ocnt++;
    }
    int ans = 0;
    if(min({Qcnt,Ocnt,Icnt}) == Qcnt){
      // printf("? small\n");
      int m1 = 0,m2 = 0,m3 = 0;
      int i = 0;
      for(auto x : a){
        if(x == '1') m1 += (1 << i);
        if(x == '?') m2 += (1 << i);
        i++;
      }
      m3 = m2;
      while(m3 > 0){
        ans += s[m3 + m1] - '0';
        m3 = (m3 - 1) & m2;
      }
      ans += s[m1] - '0';
    }else if(min({Qcnt,Ocnt,Icnt}) == Icnt){
      // printf("1 small\n");
      int m1 = 0,m2 = 0,m3 = 0;
      int i = 0;
      for(auto x : a){
        if(x == '?') m1 += (1 << i);
        if(x == '1') m2 += (1 << i);
        i++;
      }
      m3 = m2;
      while(m3 > 0){
        if(((Icnt + Qcnt) &1) == (__builtin_popcount(m3 + m1) & 1)) ans += sos[m3 + m1][(n - 1) & 1][0];
        else ans -= sos[m3 + m1][(n - 1) & 1][0];
        m3 = (m3 - 1) & m2;
      }
      if(((Icnt + Qcnt) & 1) == (__builtin_popcount(m1) & 1)) ans += sos[m1][(n - 1) & 1][0];
      else ans -= sos[m1][(n - 1) & 1][0];
    }else{
      // printf("0 small\n");
      int m1 = 0,m2 = 0,m3 = 0;
      int i = 0;
      for(auto x : a){
        if(x == '1') m1 += (1 << i);
        if(x == '0') m2 += (1 << i);
        i++;
      }
      m3 = m2;
      while(m3 > 0){
        if((Icnt & 1) == (__builtin_popcount(m3 + m1) &1)) ans += sos[m3 + m1][(n - 1) & 1][1];
        else ans -= sos[m3 + m1][(n - 1) & 1][1];
        m3 = (m3 - 1) & m2;
      }
      if((Icnt & 1) == (__builtin_popcount(m1) &1)) ans += sos[m1][(n - 1) & 1][1];
      else ans -= sos[m1][(n - 1) & 1][1];
    }
    cout<<ans<<'\n';
  }
}

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