Submission #527955

#	Time	Username	Problem	Language	Result	Execution time	Memory
527955		AdamGS	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	840 ms	54668 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
const int LIM=1<<20;
int T[LIM], ans[LIM], n, q;
pair<ll,int>pyt[LIM];
void solve(int l, int r, ll k, int a, int b) {
    if(l==r) {
        while(a<=b) {
            ans[pyt[a].nd]=T[l];
            ++a;
        }
        return;
    }
    int x=a;
    while(x<=b && (pyt[x].st/k)%3==0) ++x;
    if(x>a) solve(l, (l+r)/2, k/3, a, x-1);
    int y=x;
    while(y<=b && (pyt[y].st/k)%3==1) ++y;
    if(y>x) solve((l+r)/2+1, r, k/3, x, y-1);
    if(y<=b) {
        rep(i, (r-l+1)/2) T[l+i]+=T[(l+r)/2+1+i];
        solve(l, (l+r)/2, k/3, y, b);
        rep(i, (r-l+1)/2) T[l+i]-=T[(l+r)/2+1+i];
    }
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    string s;
    cin >> n >> q >> s;
    ll k=1;
    rep(i, n-1) k*=3;
    n=1<<n;
    rep(i, n) T[i]=s[i]-'0';
    rep(i, q) {
        string a;
        cin >> a;
        for(auto j : a) {
            pyt[i].st*=3;
            if(j=='?') pyt[i].st+=2;
            else pyt[i].st+=j-'0';
        }
        pyt[i].nd=i;
    }
    sort(pyt, pyt+q);
    solve(0, n-1, k, 0, q-1);
    rep(i, q) cout << ans[i] << '\n';
}

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