제출 #1124589

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124589		fgdsa	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1756 ms	36196 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int MAXN = 20;
vector<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 pier(string & s, vector<int> & poz, char c, vector<ll> & dp){
    ll maska = 0;

    for(int i = 0; i < s.size(); ++i){
        if(s[i] == c) 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 += dp[curMaska]*(cnt % 2 == 0 ? 1 : -1);
    }

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

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


	vector<ll> sup(1<<MAXN);
	vector<ll> sub(1<<MAXN);
    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 < 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) pier(s2, zer, '1', sup);
        else pier(s2, jed, '?', sub);
    }

    return 0;
}

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