Submission #1162898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162898		sitablechair	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	463 ms	20816 KiB

snake_escaping

#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);


using namespace std;


int n,q,dp[(1<<20)],dp1[(1<<20)];
int a[1<<20];
int cal1(string &s) {
    int t=0,t1=0,ans=0;
    For(i,0,n-1)
        if(s[i]=='0') t+=1<<i;
        else if (s[i]=='1') t1+=1<<i;
    bool k=__builtin_popcount(t)&1;
    for(int i=t;i>0;i=(i-1)&t) {
        bool k1=__builtin_popcount(i)&1;
        if (k1^k) ans-=dp1[t1+t-i];
        else ans+=dp1[t1+t-i];
    }
    if (k) ans-=dp1[t1+t];
    else ans+=dp1[t1+t];
    return ans;
}
int cal2(string &s) {
    int t=0,t1=0,ans=0;
    For(i,0,n-1)
        if(s[i]=='1') t+=1<<i;
        else if (s[i]=='?') t1+=1<<i;
    bool k=__builtin_popcount(t)&1;
    for(int i=t;i>0;i=(i-1)&t) {
        bool k1=__builtin_popcount(i)&1;
        if (k1^k) ans-=dp[t1+i];
        else ans+=dp[t1+i];
    }
    if (k) ans-=dp[t1];
    else ans+=dp[t1];
    return ans;
}
int cal3(string &s) {
    int t=0,t1=0,ans=0;
    For(i,0,n-1)
        if (s[i]=='?') t+=1<<i;
        else if(s[i]=='1') t1+=1<<i;
    for(int i=t;i>0;i=(i-1)&t)
        ans+=a[t1+i];
    ans+=a[t1];
    return ans;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    For(i,0,(1<<n)-1) {
        char c;
        cin >> c;
        a[i]=c-'0';
        dp[i]=c-'0';
        dp1[i]=c-'0';
    }
    for(int i = 0;i < n; ++i)
        for(int mask = 0; mask < (1<<n); ++mask){
            if(mask & (1<<i))
                dp[mask] += dp[mask^(1<<i)];
            else dp1[mask] += dp1[mask^(1<<i)];
        }

    while(q--) {
        string s;
        cin >> s;
        reverse(all(s));
        int cnt1=0,cnt2=0,cnt3=0;
        for(auto c: s)
            if (c=='0') cnt1++;
            else if (c=='1') cnt2++;
            else cnt3++;
        int mi=min({cnt1,cnt2,cnt3});
        if(cnt1==mi) cout << cal1(s) << endl;
        else if (cnt2==mi) cout << cal2(s) << endl;
        else cout << cal3(s) << endl;
    }
    return 0;
}

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