Submission #1098554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098554		Tame	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	444 ms	47600 KiB

snake_escaping

#include <bits/stdc++.h>
#define pu push
#define pf push_front
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fi first
#define se second
#define el cout<<"\n"
#define ll long long
#define ld long double
#define MASK(i) (1LL<<(i))
#define BIT(x, i) (((x)>>(i))&1)
#define SET_ON(x, i) ((x)|MASK(i))
#define SET_OFF(x, i) ((x)&~MASK(i))
#define c_bit(i) __builtin_popcount(i)
const int MAX_SIZE = 1100000;
const int inf = (int)1e9+7;
using namespace std;

template<class T1, class T2>
    bool maximize(T1 &x, T2 y){if(x<y){x=y; return true;} return false;}
template<class T1, class T2>
    bool minimize(T1 &x, T2 y){if(x>y){x=y; return true;} return false;}

int L, Q;
int poison[MAX_SIZE], sup[MAX_SIZE], sub[MAX_SIZE], cntbit[MAX_SIZE];
string s;

void init(){
    cin>>L>>Q>>s;
}

void ilovesunshine(){
    init();

    for (int mask=0; mask<MASK(L); mask++){
        poison[mask] = s[mask]-'0';
        sup[mask] = sub[mask] = poison[mask];
        cntbit[mask] = c_bit(mask);
    }

    for (int i=0; i<L; i++){
        for (int mask=0; mask<MASK(L); mask++){
            if (!BIT(mask, i)){
                sup[mask]+=sup[mask^(1<<i)];
            }
            else sub[mask]+=sub[mask^(1<<i)];
        }
    }

    while (Q--){
        cin>>s;
//        cout<<s<<"\n";
        int A=0, B=0, C=0, ca=0, cb=0, cc=0; ll res=0;
        for (int i=0; i<L; i++){
            if (s[i]=='0'){
                A=SET_ON(A, L-i-1);
                ca++;
            }
            else if (s[i]=='1'){
                 B=SET_ON(B, L-i-1);
                cb++;
            }
            else{
                 C=SET_ON(C, L-i-1);
                cc++;
            }
        }

        if (ca<=cb && ca<=cc){
            for (int s=A; s!=0; s=(s-1)&A){
                res += (1-2*((cntbit[s])&1))*sup[B|s];
            }
            res+=sup[B];
        }
        else if (cb<=ca && cb<=cc){
            for (int s=B; s!=0; s=(s-1)&B){
                res += (1-2*((cntbit[s])&1))*sub[C|(B^s)];
            }
            res+=sub[C|B];
        }
        else{
            for (int s=C; s!=0; s=(s-1)&C){
                res+=poison[s|B];
            }
            res+=poison[B];
        }
        cout<<res<<"\n";
    }

//    for (int mask=0; mask<MASK(L); mask++){
//        cout<<poison[mask]<<' '<<sup[mask]<<' '<<sub[mask]<<' '<<cntbit[mask]<<"\n";
//    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    freopen("bdbang.INP", "r", stdin);
//    freopen("bdbang.OUT", "w", stdout);
    ilovesunshine();
    return 0;
}

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