oj.uz

Submission #886674

# Submission time Handle Problem Language Result Execution time Memory
886674 2023-12-12T15:59:10 Z CDuong Brperm (RMI20_brperm) C++17
0 / 100
 3000 ms 45544 KB 
#include "brperm.h"
#include<bits/stdc++.h>

using namespace std;

const int base = 29;
const int mod = 1069177027;
const int mxN = 5e5 + 5;

int n, a[mxN];
vector<int> rev[20];
int a_hash[mxN], rev_hash[20][mxN], pw[mxN];

int get_hash(int l, int r) {
    return (l == 0 ? a_hash[r] : (a_hash[r] - (1ll * a_hash[l - 1] * pw[r - l + 1] % mod) + mod)) % mod;
}

int reverse_msk(int len, int msk) {
    int res = 0;
    for (int i = 0; i < len; ++i) {
        res = res << 1 | (msk & 1);
        msk >>= 1;
    }
    return res;
}

void init(int N, const char S[]) {
    n = N;
    for (int i = 0; i < N; ++i) {
        a[i] = S[i] - 'a';
        a_hash[i] = (1ll * (i ? a_hash[i - 1] : 0) * base + a[i]) % mod;
        pw[i] = (i ? 1ll * pw[i - 1] * base % mod : 1ll);
    }
    for (int len = 1; len <= 18; ++len) {
        rev[len].resize(1 << len);
        for (int msk = 0; msk < 1 << (len - len / 2); ++msk) {
            rev[len][msk] = reverse_msk(len, msk);
        }
        for (int st = 0; st + rev[len].back() <= N; ++st) {
            int cur_hash = 0;
            for (int i = 0; i < 1 << (len - len / 2); ++i)
                cur_hash = (1ll * cur_hash * base + a[st + rev[len][i]]) % mod;
            rev_hash[len][st] = cur_hash;
        }
    }
}

int query(int st, int k) {
    if (k == 0) {
        return 1;
    }
    for (int i = 0; i < 1 << (k / 2); ++i) {
        int ahead = (1 << (k - k / 2)) * i;
        int nst = st + ahead;
        if (get_hash(nst, nst + (1 << (k - k / 2)) - 1) != rev_hash[k][st + reverse_msk(k, ahead)])
            return 0;
    }
    return 1;
}

// int st, k;
// char c[mxN];

// int main() {
//     cin >> n >> c;
//     init(n, c);
//     while (cin >> st >> k) {
//         cout << query(st, k) << "\n";
//     }
// }

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 45404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 45404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

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

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 45404 KB Output isn't correct
2 Halted 0 ms 0 KB -