Submission #872862

#	Time	Username	Problem	Language	Result	Execution time	Memory
872862		azberjibiou	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	943 ms	54864 KiB

snake_escaping

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=1100005;
const int mxM=500004;
const int mxK=30;
const int MOD=1'000'000'007;
const ll INF=8e18;
int L, Q;
char B[mxN];
int A[mxN];
char qry[mxK];
int dp1[mxN], dp0[mxN];
int one[mxN], oi;
int zero[mxN], zi;
int oz[mxN], ozi;
int pc[mxN];    ///popcount
void input(){
    cin >> L >> Q;
    cin >> B;
    for(int i=0;i<(1<<L);i++) A[i]=B[i]-'0';
}
void precalc(){
    for(int i=0;i<(1<<L);i++)   pc[i]=__builtin_popcount(i)%2;
    for(int i=0;i<(1<<L);i++)   dp1[i]=dp0[i]=A[i];
    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)];
            else dp0[j]+=dp0[j^(1<<i)];
        }
    }
}
void solv_one(){
    ll res=0;
    int idx=0;
    for(int i=0;i<L;i++)    if(qry[i]=='?') idx+=(1<<i);
    int M=(1<<oi)-1;
    for(int i=0;i<(1<<oi);i++){
        int ni=0;
        for(int j=0;j<oi;j++){
            if((1<<j)&i)    ni+=(1<<one[j]);
        }
        //printf("idx=%d, ni=%d\n", idx, ni);
        if(pc[i^M]==0)    res+=dp1[idx+ni];
        else    res-=dp1[idx+ni];
    }
    cout << res << '\n';
}
void solv_zero(){
    ll res=0;
    int idx=0;
    int M=(1<<zi)-1;
    for(int i=0;i<L;i++)    if(qry[i]=='?') idx+=(1<<i);
    for(int i=0;i<(1<<zi);i++){
        int ni=0;
        for(int j=0;j<zi;j++){
            if((1<<j)&i)    ni+=(1<<zero[j]);
        }
        //printf("idx=%d, ni=%d\n", idx, ni);
        if(pc[i^M]==0)    res+=dp0[(1<<L)-1-idx-ni];
        else    res-=dp0[(1<<L)-1-idx-ni];
    }
    cout << res << '\n';
}
void solv_oz(){
    ll res=0;
    int idx=0;
    for(int i=0;i<L;i++)    if(qry[i]=='1') idx+=(1<<i);
    for(int i=0;i<(1<<ozi);i++){
        int ni=0;
        for(int j=0;j<ozi;j++){
            if((1<<j)&i)    ni+=(1<<oz[j]);
        }
        res+=A[ni+idx];
    }
    cout << res << '\n';
}
int main()
{
    gibon
    input();
    precalc();
    while(Q--){
        cin >> qry;
        reverse(qry, qry+L);
        oi=zi=ozi=0;
        for(int i=0;i<L;i++){
            if(qry[i]=='1') one[oi++]=i;
            if(qry[i]=='0') zero[zi++]=i;
            if(qry[i]=='?') oz[ozi++]=i;
        }
        if(oi<=zi && oi<=ozi)   solv_one();
        else if(zi<=oi && zi<=ozi)  solv_zero();
        else    solv_oz();
    }
}

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