Submission #465429

#	Time	Username	Problem	Language	Result	Execution time	Memory
465429		czhang2718	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1051 ms	43360 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;

#define nl '\n'

int l, q;
string a;
int dp1[1<<20];
int dp0[1<<20];
int cnt[2];
int bits[1<<20];

string bin(int i){
  string s;
  for(int j=0; j<l; j++){
      if(i&(1<<j)) s+='1';
      else s+='0';
    }
    return s;
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);

  cin >> l >> q;
  cin >> a;

  for(int i=0; i<(1<<l); i++){
    dp1[i]=a[i]-'0';
    dp0[i]=a[((1<<l)-1)^i]-'0';
  }

  for(int i=0; i<l; i++){
    for(int j=0; j<(1<<l); j++){
      if(!(j&(1<<i))) dp1[j]+=dp1[j^(1<<i)];
      if(!(j&(1<<i))) dp0[j]+=dp0[j^(1<<i)];
    }
  }
  for(int i=0; i<(1<<l); i++){
    for(int j=0; j<l; j++){
      if(i&(1<<j)) bits[i]++;
    }
  }

  string s;
  while(q--){
    cin >> s;
    reverse(s.begin(), s.end());
    cnt[0]=cnt[1]=cnt[2]=0;
    int m0=0;
    int m1=0;
    int m2=0;
    for(int i=0; i<l; i++){
      if(s[i]=='?') cnt[2]++, m2^=(1<<i);
      else if(s[i]=='1') cnt[1]++, m1^=(1<<i);
      else cnt[0]++, m0^=(1<<i);
    }
    int ans;
    if(cnt[0]<cnt[1] && cnt[0]<cnt[2]){
      // fix 1s, iterate over submasks of 0s
      ans=dp1[m1];
      for(int s=m0; s; s=(s-1)&m0){
        ans+=(bits[s]&1?-1:1)*dp1[m1|s];
      }
    }
    else if(cnt[1]<cnt[2]){
      ans=dp0[m0];
      for(int s=m1; s; s=(s-1)&m1){
        ans+=(bits[s]&1?-1:1)*dp0[m0|s];
      }
    }
    else{
      ans=a[m1]-'0';
      for(int s=m2; s; s=(s-1)&m2){
        ans+=a[m1|s]-'0';
      }
      if(!cnt[2]) ans=a[m1]-'0';
    }

    cout << ans << nl;
  }
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:51:24: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
   51 |     cnt[0]=cnt[1]=cnt[2]=0;
      |                   ~~~~~^
snake_escaping.cpp:10:5: note: while referencing 'cnt'
   10 | int cnt[2];
      |     ^~~
snake_escaping.cpp:56:26: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
   56 |       if(s[i]=='?') cnt[2]++, m2^=(1<<i);
      |                     ~~~~~^
snake_escaping.cpp:10:5: note: while referencing 'cnt'
   10 | int cnt[2];
      |     ^~~
snake_escaping.cpp:56:26: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
   56 |       if(s[i]=='?') cnt[2]++, m2^=(1<<i);
      |                     ~~~~~^
snake_escaping.cpp:10:5: note: while referencing 'cnt'
   10 | int cnt[2];
      |     ^~~
snake_escaping.cpp:61:37: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
   61 |     if(cnt[0]<cnt[1] && cnt[0]<cnt[2]){
      |                                ~~~~~^
snake_escaping.cpp:10:5: note: while referencing 'cnt'
   10 | int cnt[2];
      |     ^~~
snake_escaping.cpp:68:25: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
   68 |     else if(cnt[1]<cnt[2]){
      |                    ~~~~~^
snake_escaping.cpp:10:5: note: while referencing 'cnt'
   10 | int cnt[2];
      |     ^~~

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