oj.uz

Submission #527947

# Submission time Handle Problem Language Result Execution time Memory
527947 2022-02-18T20:21:45 Z AdamGS Snake Escaping (JOI18_snake_escaping) C++17
0 / 100
 2000 ms 41416 KB 
#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<string,int>pyt[LIM];
void solve(int l, int r, int k, int a, int b) {
    if(k==n) {
        while(a<=b) {
            ans[pyt[a].nd]=T[l];
            ++a;
        }
        return;
    }
    int x=a;
    while(pyt[x].st[k]=='0') ++x;
    if(x>a) solve(l, (l+r)/2, k+1, a, x-1);
    int y=x;
    while(pyt[y].st[k]=='1') ++y;
    if(y>x) solve((l+r)/2+1, r, k+1, 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+1, 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;
    n=1<<n;
    rep(i, n) T[i]=s[i]-'0';
    rep(i, q) {
        cin >> pyt[i].st;
        pyt[i].nd=i;
    }
    sort(pyt, pyt+q);
    solve(0, n-1, 0, 0, q-1);
    rep(i, q) cout << ans[i] << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 41416 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 41416 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 41416 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 41416 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 41416 KB Time limit exceeded
2 Halted 0 ms 0 KB -