Submission #1166854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166854		davele	Snake Escaping (JOI18_snake_escaping)	C++20	22 / 100	214 ms	26300 KiB

snake_escaping

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define vi vector <int>
#define pq priority_queue
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define x0 ___x0
#define y0 ___y0
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define pos pisosi
#define pb push_back
#define pf push_front
using namespace std;

//const int mod = ;
//void add (int &a, const int&b){
//    a+=b;
//    if (a>=mod) a-=mod;
//}
//
//void sub (int&a, const int&b){
//    a-=b;
//    if (a<0) a+=mod;
//}
//
//void mul (int&a, const int&b){
//    a*=b;
//    a%=mod;
//}

template<class X, class Y>
    bool minimize(X &x, const Y&y){
        if (x<=y) return false;
        else{
            x = y;
            return true;
        }
    }
template<class X, class Y>
    bool maximize (X &x, const Y&y){
        if (x>=y) return false;
        else{
            x = y;
            return true;
        }
    }

/////////////////////////////////////////////////////////////////////////////////

//// dang nhap ham
//#ifndef davele
//
//#endif // davele
//
//// chay thu ham main:
//
//#ifdef davele
//
//#endif // davele

////////////////////////////////////////////////////////////////////////////
const int lim = 11e5, limit = lim+5;

int k,q, dp[limit], dp2[limit];
string s;
int allmask;
int A[limit];

void prep(){
    for (int i=0; i<=allmask; i++) dp[i] = dp2[i] = A[i];
    for (int i=0; i<k; i++){
        for (int mask = allmask; mask>=0; mask--){
            if (MASK(i)&mask) dp[mask] += dp[mask^MASK(i)];
        }
        for (int mask = 0; mask<=allmask; mask++){
            if (!(MASK(i)&mask)) dp2[mask] += dp2[mask^MASK(i)];
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int bound = 6;
    //
//    freopen (".inp", "r", stdin);
//    freopen (".out", "w", stdout);
    cin>>k>>q>>s;
    allmask = MASK(k)-1;
    for (int i=0; i<=allmask; i++) A[i] = s[i]-'0';
    prep();
    while (q--){
        cin>>s;
        int b1 = 0, b0 = 0, bq = 0;
        for (int i=0; i<k; i++){
            if (s[i]=='0') b0+=MASK(k-i-1);
            else if (s[i]=='1') b1+=MASK(k-i-1);
            else bq+=MASK(k-i-1);
        }
        if (__builtin_popcount(bq)<=bound){
            int ret = A[b1];
            for (int i = bq; i>0; i = (i-1)&bq){
                ret += A[b1|i];
            }
            cout<<ret<<"\n";
//            cout<<b0<<" "<<b1<<" "<<bq<<" "<<ret<<"\n";
            continue;
        }
        if (__builtin_popcount(b1)<=bound){
            int m = __builtin_popcount(b1)%2;
            int ret = (m==0) ? dp[bq] : -dp[bq];
//            cerr<<ret<<"\n";
            for (int i = b1; i>0; i = (i-1)&b1){
                if (__builtin_popcount(i)%2!=m){
                    ret -= dp[i|bq];
                }
                else ret += dp[i|bq];
//                cerr<<ret<<"\n";
            }
            cout<<ret<<"\n";
            continue;
        }
        if (__builtin_popcount(b0)<=bound){
            int ret = dp2[bq];
            for (int i = b0; i>0; i = (i-1)&b0){
                if (__builtin_popcount(i)%2!=0){
                    ret -= dp2[i|bq];
                }
                else ret += dp2[i|bq];
            }
            cout<<ret<<"\n";
            continue;
        }
    }
}

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