Submission #1175864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175864		dosts	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	482 ms	34344 KiB

snake_escaping

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sp << " " << 
using namespace std;

const int N = 1e4+1,MOD = 1e9+7,inf = 1e18;


void solve() {
    int n,q;
    cin >> n >> q;
    int lim = (1<<n);
    string dizi;
    cin >> dizi;
    vi a(lim);
    for (int i = 0;i<lim;i++) a[i] = dizi[i]-'0';
    vi sos(a),super(a);
    for (int i = 0;i<n;i++) {
        for (int j = 0;j<lim;j++) {
            if (j&(1<<i)) sos[j]+=sos[j^(1<<i)];
            else super[j] += super[j^(1<<i)];
        }
    }
    while (q--) {
        string s;
        cin >> s;
        int sifir = count(all(s),'0');
        int bir = count(all(s),'1');
        int soru = count(all(s),'?');
        int basemask = 0,topmask = 0,zers = 0,ones = 0;
        for (int j = 0;j<n;j++) {
            if (s[j] == '1') basemask+=(1<<(n-j-1)),topmask+=(1<<(n-j-1)),ones+=(1<<(n-j-1));
            else if (s[j] == '?') topmask+=(1<<(n-j-1));
            else zers += (1<<(n-j-1));
        }
        if (sifir <= 6) {
            int ans = super[basemask];
            for (int s = zers;s > 0;s = (s-1)&zers) {
                int pc = __builtin_popcountll(s);
                if (pc%2) ans-=super[basemask^s];
                else ans+=super[basemask^s];
            }
            cout << ans << '\n';
        }
        else if (bir <= 6) {
            int ans = sos[topmask];
            for (int s = ones;s > 0;s = (s-1)&ones) {
                int pc = __builtin_popcountll(s);
                if (pc%2) ans-=sos[topmask^s];
                else ans+=sos[topmask^s];
            }
            cout << ans << '\n';
        }
        else {
            //direk iterate
            int ans = a[basemask];
            for (int s = topmask^basemask;s > 0;s=(topmask^basemask)&(s-1)) ans+=a[basemask^s];
            cout << ans << '\n';
        }
    }
};

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
} 

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