Submission #810215

#	Time	Username	Problem	Language	Result	Execution time	Memory
810215		QwertyPi	Snake Escaping (JOI18_snake_escaping)	C++14	22 / 100	2054 ms	25988 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 == 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:25:30: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   25 |     solve(L - 1, a + (1 << L - 1), mid_0, mid_1);
      |                            ~~^~~
snake_escaping.cpp:27:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   27 |     for(int i = 0; i < (1 << L - 1); i++) a[i] += a[i + (1 << L - 1)];
      |                              ~~^~~
snake_escaping.cpp:27:65: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   27 |     for(int i = 0; i < (1 << L - 1); i++) a[i] += a[i + (1 << L - 1)];
      |                                                               ~~^~~
snake_escaping.cpp:29:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   29 |     for(int i = 0; i < (1 << L - 1); i++) a[i] -= a[i + (1 << L - 1)];
      |                              ~~^~~
snake_escaping.cpp:29:65: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   29 |     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: 0 / 53
• Subtask 5: 0 / 25