Submission #1095731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095731		doducanh	Snake Escaping (JOI18_snake_escaping)	C++14	0 / 100	26 ms	16732 KiB

snake_escaping

///breaker
///every second counts
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
#define lc (id<<1)
#define rc ((id<<1)^1)
int l,q;
string s;
ll f0[(1<<20)];
ll f1[(1<<20)];
void sol(void){
    cin>>l>>q;
    cin>>s;
    for(int i=0;i<s.size();i++){
        f0[i]+=s[i]-'0';
        f1[i]+=s[i]-'0';
    }
    for(int i=0;i<20;i++){
        for(int j=0;j<(1<<20);j++)if(bit(j,i)){
            f0[j]+=f0[(j^(1<<i))];
            f1[(j^(1<<i))]+=f1[j];
        }
    }
    while(q--){
        string tmp;
        cin>>tmp;
        reverse(tmp.begin(),tmp.end());
        int a=0,b=0,c=0;
        for(int i=0;i<l;i++){
            if(tmp[i]=='0'){
                a|=(1<<i);
            }
            else if(tmp[i]=='1'){
                b|=(1<<i);
            }
            else c|=(1<<i);
        }
        ll res=0;
        if(__builtin_popcount(a)<=l/3){
            for(int i=a;i>=0;i--){
                i&=a;
                if(__builtin_popcount(i)==0){
                    res+=f1[i|b];
                }
                else res-=f1[i|b];
            }
        }
        else if(__builtin_popcount(b)<=l/3){
            for(int i=b;i>=0;i--){
                i&=b;
                if((__builtin_popcount(b)-__builtin_popcount(i)))res-=f0[i|c];
                else res+=f0[i|c];
            }
        }
        else{
            for(int i=c;i>=0;i--){
                i&=c;
                res+=(s[i|b]-'0');
            }
        }
        cout<<res<<"\n";
    }
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        sol();
    }
    // you should actually read the stuff at the bottom
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

Compilation message (stderr)

snake_escaping.cpp: In function 'void sol()':
snake_escaping.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

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