Submission #886651

#	Time	Username	Problem	Language	Result	Execution time	Memory
886651		CDuong	Brperm (RMI20_brperm)	C++17	0 / 100	3006 ms	47452 KiB

brperm

#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 <= 19; ++len) {
        rev[len].resize(1 << len);
        for (int msk = 0; msk < 1 << (len - len / 2); ++msk) {
            rev[len][msk] = reverse_msk(len, msk);
            // cout << rev[len][msk] << " ";
        }
        // cout << endl;
        for (int st = 0; st + (1 << (len - len / 2)) <= 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;
            // cout << len << " " << st << " " << rev_hash[len][st] << endl;
        }
    }
}
 
int query(int st, int k) {
  assert(k != 0);
    for (int i = 0; i < 1 << (k / 2); ++i) {
        int ahead = (1 << (k - k / 2)) * i;
        int nst = st + ahead;
        // cout << "nst = " << nst << " " << st + reverse_msk(k, ahead) << endl;
        // cout << get_hash(nst, nst + (1 << (k - k / 2)) - 1) << endl;
        // cout << rev_hash[k][st + reverse_msk(k, ahead)] << endl;
        if (get_hash(nst, nst + (1 << (k - k / 2)) - 1) != rev_hash[k][st + reverse_msk(k, ahead)])
            return 0;
    }
    return 1;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 37
• Subtask 3: 0 / 17
• Subtask 4: 0 / 33