제출 #1271374

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271374		VMaksimoski008	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1103 ms	20704 KiB

snake_escaping

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int N = 1e5 + 5;

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

    int n, q; cin >> n >> q;
    vector<int> a(1<<n);

    for(int i=0; i<(1<<n); i++) {
        char ch; cin >> ch;
        a[i] = ch - '0';
    }

    auto get_val = [&](const string &s) {
        int p = 0;
        for(int i=0; i<n; i++)
            if(s[i] == '1') p |= (1 << (n-i-1));
        return p;
    };

    vector<int> dp_up(1<<n), dp_down(1<<n);
    for(int i=0; i<(1<<n); i++)
        dp_up[i] = dp_down[i] = a[i];

    for(int i=0; i<n; i++)
        for(int s=0; s<(1<<n); s++)
            if(!(s & (1 << i))) dp_up[s] += dp_up[s^(1<<i)];

    for(int i=0; i<n; i++)
        for(int s=0; s<(1<<n); s++)
            if(s & (1 << i)) dp_down[s] += dp_down[s^(1<<i)];

    while(q--) {
        string s; cin >> s;
        map<char, int> mp;
        for(char ch : s) mp[ch]++;

        if(mp['?'] <= 6) {
            int og = get_val(s);
            vector<int> pos;
            for(int i=0; i<n; i++)
                if(s[i] == '?') pos.push_back(n-i-1);

            int m = pos.size(), ans = 0;
            for(int mask=0; mask<(1<<m); mask++) {
                int v = og;
                for(int i=0; i<m; i++)
                    if(mask & (1 << i))
                        v += (1 << pos[i]);
                ans += a[v];
            }

            cout << ans << '\n';
            continue;
        }

        if(mp['0'] <= 6) {
            int ans = 0, og = get_val(s);
            vector<int> pos;
            for(int i=0; i<n; i++)
                if(s[i] == '0') pos.push_back(n-i-1);

            int m = pos.size();
            for(int mask=0; mask<(1<<m); mask++) {
                int v = og;
                for(int i=0; i<m; i++)
                    if(mask & (1 << i)) v |= (1 << pos[i]);
                
                if(__builtin_parity(mask)) ans -= dp_up[v];
                else ans += dp_up[v];
            }

            cout << ans << '\n';
            continue;
        }

        int ans = 0, og = get_val(s);
        vector<int> pos;
        for(int i=0; i<n; i++) {
            if(s[i] == '1') pos.push_back(n-i-1);
            else if(s[i] == '?') og |= (1 << (n-i-1));
        }

        int m = pos.size();
        for(int mask=0; mask<(1<<m); mask++) {
            int v = og;
            for(int i=0; i<m; i++)
                if(mask & (1 << i)) v -= (1 << pos[i]);
                
            if(__builtin_parity(mask)) ans -= dp_down[v];
            else ans += dp_down[v];
        }

        cout << ans << '\n';
    }
}

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