Submission #810207

#	Time	Username	Problem	Language	Result	Execution time	Memory
810207		QwertyPi	Snake Escaping (JOI18_snake_escaping)	C++14	22 / 100	2076 ms	39760 KiB

snake_escaping

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

int a[1 << 20], 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, vector<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++;
    vector<int> b(1 << L - 1);
    // 0
    for(int i = 0; i < (1 << L - 1); i++) b[i] = a[i];
    solve(L - 1, b, l, mid_0);
    // 1
    for(int i = 0; i < (1 << L - 1); i++) b[i] = a[i + (1 << L - 1)];
    solve(L - 1, b, mid_0, mid_1);
    // ?
    for(int i = 0; i < (1 << L - 1); i++) b[i] = a[i] + a[i + (1 << L - 1)];
    solve(L - 1, b, mid_1, r);
}

int32_t main(){
    cin.tie(0); cout.tie(0)->sync_with_stdio(false);
    int L, q; cin >> L >> q; string s; cin >> s;
    vector<int> a(1 << L); 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, std::vector<int>, int, int)':
snake_escaping.cpp:22:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   22 |     vector<int> b(1 << L - 1);
      |                        ~~^~~
snake_escaping.cpp:24:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   24 |     for(int i = 0; i < (1 << L - 1); i++) b[i] = a[i];
      |                              ~~^~~
snake_escaping.cpp:27:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   27 |     for(int i = 0; i < (1 << L - 1); i++) b[i] = a[i + (1 << L - 1)];
      |                              ~~^~~
snake_escaping.cpp:27:64: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   27 |     for(int i = 0; i < (1 << L - 1); i++) b[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++) b[i] = a[i] + a[i + (1 << L - 1)];
      |                              ~~^~~
snake_escaping.cpp:30:71: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   30 |     for(int i = 0; i < (1 << L - 1); i++) b[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