제출 #1306045

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306045		ladnoooo	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1368 ms	26068 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define int long long

const int maxN = 2e6 + 7;

int dp[maxN], cp[maxN];

void solve() {
    /*int n, m;
    cin >> n >> m;
    vector<pair<int, int>> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a.begin(), a.end());
    
    if(m > n / 2) {
        cout << -1 << '\n';
        return;
    }

    vector<pair<int, int>> ans;

    int pos = n - 1;

    for(int i = 0; i < n; i++) {
        if(i >= pos) break;
        ans.pb({a[pos--].second, a[i].second});
    }

    cout << ans.size() << '\n';
    for(auto [x, y] : ans) {
        cout << x + 1 << ' ' << y + 1 << '\n';
    }*/

    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int big = 1 << n;
    for(int i = 0; i < big; i++) {
        cp[i] = s[i] - '0';
        dp[i] = s[i] - '0';
    }

    for(int i = 0; i < n; i++) {
        for(int msk = 0; msk < big; msk++) {
            if(!(msk & (1 << i))) dp[msk] += dp[msk ^ (1 << i)];
        }
    }

    while(k--) {
        string q;
        cin >> q;
        int a = 0, b = 0, c = 0, z = 0;
        for(int i = 0; i < n; i++) {
            int m = 1 << i;
            char ch = q[n - i - 1];
            a |= (ch == '1') * m;
            b |= (ch == '0') * m;
            c |= (ch == '?') * m;
            z += (ch == '0');
        }

        int ans = 0;

        if(z < __builtin_popcount(c)) {
            int s = b;
            while(true) {
                ans += (__builtin_popcount(s) % 2 == 0 ? dp[a | s] : -dp[a | s]);
                if(s == 0) break;
                s = (s - 1) & b;
            }
        } else {
            int s = c;
            while(true) {
                ans += cp[a | s];
                if(s == 0) break;
                s = (s - 1) & c;
            }
        }
        cout << ans << '\n';
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("input.txt", "r", stdin);
    int t = 1;
    //cin >> t;
    while(t--) solve();
}

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