Submission #1123895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123895		fgdsa	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1511 ms	34248 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int MAXN = 20;

ll sup[1<<MAXN];
ll sub[1<<MAXN];
ll init[1<<MAXN];

void brut(string & s, vector<int> & poz){
    ll res = 0;
    ll initMask = 0;
    for(int i = 0; i < s.size(); ++i){
        if(s[i] == '1') initMask ^= (1<<i);
    }

    for(int i = 0; i < (1<<poz.size()); ++i){
        ll curMask = initMask;
        for(int j = 0; j < poz.size(); ++j){
            if(i & (1<<j)) curMask |= (1<<poz[j]);
        }
        res += init[curMask];
    }

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

void pier0(string & s, vector<int> & poz){
    ll maska = 0;

    for(int i = 0; i < s.size(); ++i){
        if(s[i] == '1') maska |= (1<<i);
    }

    ll res = 0;

    for(int i = 0; i < (1<<poz.size()); ++i){
        ll curMaska = maska;
        ll cnt = 0;
        for(int j = 0; j < poz.size(); ++j){
            if(i & (1 << j)) curMaska |= (1<<poz[j]), ++cnt;
        }   
        res += sup[curMaska]*(cnt % 2 == 0 ? 1 : -1);
    }

    cout << abs(res) << "\n";
}

void pier1(string & s, vector<int> & poz){
    ll maska = 0;

    for(int i = 0; i < s.size(); ++i){
        if(s[i] == '?') maska |= (1<<i);
    }

    ll res = 0;

    for(int i = 0; i < (1<<poz.size()); ++i){
        ll curMaska = maska;
        ll cnt = 0;
        for(int j = 0; j < poz.size(); ++j){
            if(i & (1 << j)) curMaska |= (1<<poz[j]), ++cnt;
        }   
        res += sub[curMaska]*((cnt % 2) ? -1 : 1);
    }

    cout << abs(res) << "\n";
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;

    for(int i = 0; i < (1<<n); ++i) sup[i] = sub[i] = init[i] = (s[i] - '0');

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < (1<<n); ++j){
            if(j & (1<<i)){
                sub[j] += sub[j ^ (1<<i)];
            }
            else{
                sup[j] += sup[j ^ (1<<i)];
            }
        }
    }

    // for(int i = 0; i < (1<<n); ++i) cerr << i << ": " << sup[i] << "\n";

    for(int i = 0; i < q; ++i){
        string s2;
        cin >> s2;

        reverse(s2.begin(), s2.end());

        vector<int> jed, zer, pyt;
        for(int j = 0; j < s2.size(); ++j){
            if(s2[j] == '1') jed.push_back(j);
            if(s2[j] == '0') zer.push_back(j);
            if(s2[j] == '?') pyt.push_back(j);
        }

        if(pyt.size() <= n/3) brut(s2, pyt);
        else if(zer.size() <= n/3) pier0(s2, zer);
        else pier1(s2, jed);
    }

    return 0;
}

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