Submission #1231642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231642		duyngadocton	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1235 ms	21844 KiB

snake_escaping

#include<bits/stdc++.h>

using namespace std;

const int MAX  = (int) 2e6;

#define pb push_back

int l, q;
string s;
int a[MAX + 5];
int f[1 << 21], g[1 << 21];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> l >> q;
    cin >> s;
    for(int i = 0; i < (1 << l); ++i) a[i] = s[i] - '0';
    for(int i = 0; i < (1 << l); ++i) f[i] = a[i];
    for(int i = 1; i <= l; ++i)
        for(int mask = 0; mask < (1 << l); ++mask) if(mask >> (i - 1) & 1) f[mask] += f[mask ^ (1 << (i - 1))];
    for(int i = 0; i < (1 << l); ++i) g[(1 << l) - i - 1] = a[i];
    for(int i = 1; i <= l; ++i)
        for(int mask = 0; mask < (1 << l); ++mask) if(mask >> (i - 1) & 1) g[mask] += g[mask ^ (1 << (i - 1))];
    reverse(g, g + (1 << l));
    while(q--) {
        string t;
        cin >> t;
        vector<int> v0, v1, v2;
        int cur = 0;
        int cur2 = 0;
        for(int i = l - 1; i >= 0; --i) if(t[i] == '0') v0.pb((1 << (l - i - 1)));
        else if(t[i] == '1') v1.pb(1 << (l - i - 1)), cur += (1 << (l - i - 1));
        else v2.pb((1 << (l - i - 1))), cur2 += 1 << (l - i - 1);
        cur2 += cur;
        int ds = 0;
        if(v0.size() <= 6) {
            int m = v0.size();
            for(int mask = 0; mask < (1 << m); ++mask) {
                int hs = 1;
                if(__builtin_popcount(mask) % 2) hs = -1;
                int A = 0;
                for(int i = 0; i < m; ++i) if(mask >> i & 1) {
                    A += v0[i];
                }
                ds += hs * g[cur + A];
            }
            cout << ds << "\n";
        }
        else
            if(v1.size() <= 6) {
            int m = v1.size();
            for(int mask = 0; mask < (1 << m); ++mask) {
                int hs = 1;
                if(__builtin_popcount(mask) % 2) hs = -1;
                int A = 0;
                for(int i = 0; i < m; ++i) if(mask >> i & 1) {
                    A += v1[i];
                }
                ds += hs * f[cur2 - A];
            }
            cout << ds << "\n";
        }
        else {
            int m = v2.size();
            for(int mask = 0; mask < (1 << m); ++mask) {
                int A = 0;
                for(int i = 0; i < m; ++i) if(mask >> i & 1)
                    A += v2[i];
                ds += a[A + cur];
            }
            cout << ds << "\n";
        }
    }
}

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