Submission #810217

#	Time	Username	Problem	Language	Result	Execution time	Memory
810217		QwertyPi	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	849 ms	55592 KiB

snake_escaping

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

int ans[1 << 20];
int f(char c){
    if(c == '0') return 0;
    if(c == '1') return 1;
    if(c == '?') return 2;
    return -1;
}

vector<pair<long long, int>> Q;
void solve(int L, int* a, int l, int r){
    if(l == r) return;
    if(L == 0){
        for(int i = l; i < r; i++){
            ans[Q[i].second] = a[0];
        }
        return;
    }
    int mid_0 = l; while(mid_0 < r && (Q[mid_0].first & (3LL << (L - 1) * 2)) == 0) mid_0++;
    int mid_1 = mid_0; while(mid_1 < r && ((Q[mid_1].first & (3LL << (L - 1) * 2)) >> (L - 1) * 2) == 1) mid_1++;
    // 0
    solve(L - 1, a, l, mid_0);
    // 1
    solve(L - 1, a + (1 << L - 1), mid_0, mid_1);
    // ?
    for(int i = 0; i < (1 << L - 1); i++) a[i] += a[i + (1 << L - 1)];
    solve(L - 1, a, mid_1, r);
    for(int i = 0; i < (1 << L - 1); i++) a[i] -= a[i + (1 << L - 1)];
}

int a[1 << 20];
int32_t main(){
    cin.tie(0); cout.tie(0)->sync_with_stdio(false);
    int L, q; cin >> L >> q; string s; cin >> s;
    for(int i = 0; i < (1 << L); i++) a[i] = s[i] - '0';
    for(int i = 0; i < q; i++){
        string s; cin >> s; reverse(s.begin(), s.end());
        long long b = 0;
        for(int j = 0; j < L; j++){
            b |= f(s[j]) * (1LL << j * 2);
        }
        Q.push_back({b, i});
    }
    sort(Q.begin(), Q.end());
    solve(L, a, 0, Q.size());

    for(int i = 0; i < q; i++){
        cout << ans[i] << '\n';
    }
}

Compilation message (stderr)

snake_escaping.cpp: In function 'void solve(int, int*, int, int)':
snake_escaping.cpp:26:30: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   26 |     solve(L - 1, a + (1 << L - 1), mid_0, mid_1);
      |                            ~~^~~
snake_escaping.cpp:28:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   28 |     for(int i = 0; i < (1 << L - 1); i++) a[i] += a[i + (1 << L - 1)];
      |                              ~~^~~
snake_escaping.cpp:28:65: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   28 |     for(int i = 0; i < (1 << L - 1); i++) a[i] += a[i + (1 << L - 1)];
      |                                                               ~~^~~
snake_escaping.cpp:30:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   30 |     for(int i = 0; i < (1 << L - 1); i++) a[i] -= a[i + (1 << L - 1)];
      |                              ~~^~~
snake_escaping.cpp:30:65: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   30 |     for(int i = 0; i < (1 << L - 1); i++) a[i] -= a[i + (1 << L - 1)];
      |                                                               ~~^~~

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