Submission #1113364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113364		emad234	Snake Escaping (JOI18_snake_escaping)	C++17	75 / 100	2071 ms	23140 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");
      for(int mask = 0;mask < (1 << Qcnt);mask++){
        int cnt = 0;
        int num = 0;
        int i = 0;
        for(auto x : a){
          if(x == '?') {
            if(mask >> cnt & 1) num += (1 << i);
              cnt++;
          }
          if(x == '1') num += (1 << i);
          i++;
        }
        ans += s[num] - '0';
      }
    }else if(min({Qcnt,Ocnt,Icnt}) == Icnt){
      // printf("1 small\n");
      for(int mask = 0; mask < (1 << Icnt);mask++){
        int cnt = 0;
        int num = 0;
        int i = 0;
        for(auto x : a){
          if(x == '1') {
            if(mask >> cnt & 1) num += (1 << i);
              cnt++;
          }
          if(x == '?') num += (1 << i);
          i++;
        }
        if((Icnt &1) == (__builtin_popcount(mask) &1)) ans += sos[num][(n - 1)&1][0];
        else ans -= sos[num][(n - 1)&1][0];
      }
    }else{
      for(int mask = 0; mask < (1 << Ocnt);mask++){
        // printf("0 small\n");
        int cnt = 0;
        int num = 0;
        int i = 0;
        for(auto x : a){
          if(x == '0') {
            if(mask >> cnt & 1) num += (1 << i);
              cnt++;
          }
          if(x == '1') num += (1 << i);
          // if(x == '?') num += (1 << i);
          i++;
        }
        if(0 == (__builtin_popcount(mask) & 1)) ans += sos[num][(n - 1)&1][1];
        else ans -= sos[num][(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: 0 / 25