Submission #415911

#	Time	Username	Problem	Language	Result	Execution time	Memory
415911		nvmdava	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1293 ms	47392 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1050005;
const ll MOD = 1000000007;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int SQ = 300;

string s;
int sc[N];
int s1[N], s0[N], bc[N];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin>>n>>q;
    cin>>s;
    for(int i = 0; i < (1 << n); ++i)
        sc[i] = s[i] - '0';

    for(int i = 1; i < (1 << n); ++i)
        bc[i] = bc[i - (i & -i)] + 1;

    for(int i = 0; i < (1 << n); ++i)
        s1[i] = sc[i];
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < (1 << n); ++j)
            if((j & (1 << i)) == 0)
                s1[j] += s1[j | (1 << i)];

    for(int i = 0; i < (1 << n); ++i)
        s0[i] = sc[((1 << n) - 1) ^ i];
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < (1 << n); ++j)
            if((j & (1 << i)) == 0)
                s0[j] += s0[j | (1 << i)];

    while(q--){
        cin>>s;
        int t1 = 0, t0 = 0, t2 = 0;
        for(int i = 0; i < n; ++i){
            if(s[i] == '1') t1 |= (1 << (n - 1 - i));
            if(s[i] == '0') t0 |= (1 << (n - 1 - i));
            if(s[i] == '?') t2 |= (1 << (n - 1 - i));
        }
        int res = 0;
        if(bc[t2] <= 7){
            for(int i = t2; ; i = (i - 1) & t2){
                res += sc[t1 | i];
                if(i == 0) break;
            }
            cout<<res<<'\n';
        } else
        if(bc[t0] <= 7){
            for(int i = t0; ; i = (i - 1) & t0){
                res += s1[t1 | i] * (bc[i] & 1 ? -1 : 1);
                if(i == 0) break;
            }
            cout<<res<<'\n';
        } else
        if(bc[t1] <= 7){
            for(int i = t1; ; i = (i - 1) & t1){
                res += s0[t0 | i] * (bc[i] & 1 ? -1 : 1);
                if(i == 0) break;

            }
            cout<<res<<'\n';
        }
    }
}

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