Submission #474475

#	Time	Username	Problem	Language	Result	Execution time	Memory
474475		Alexandruabcde	Brperm (RMI20_brperm)	C++14	100 / 100	344 ms	81324 KiB

brperm

#include "brperm.h"

constexpr int BASE = 31;
constexpr int MOD = 1e9 + 7;
constexpr int NMAX = 5e5 + 5;

int Power_Base[NMAX];
int Normal_Hash[21][NMAX];
int BrPerm_Hash[21][NMAX];
int Max_Pow = 19;

void init(int n, const char s[]) {
    Power_Base[0] = BASE;
    for (int i = 1; i <= Max_Pow; ++ i )
        Power_Base[i] = (1LL * Power_Base[i-1] * Power_Base[i-1]) % MOD;
    for (int i = 0; i < n; ++ i )
        BrPerm_Hash[0][i] = s[i] - 'a';

    for (int k = 1; k <= Max_Pow; ++ k )
        for (int i = 0; i + (1<<k) - 1 < n; ++ i )
            BrPerm_Hash[k][i] = (1LL * BrPerm_Hash[k-1][i] + (1LL * BrPerm_Hash[k-1][i+(1<<(k-1))] * Power_Base[Max_Pow-k]) % MOD) % MOD;

    for (int k = 0; k <= Max_Pow; ++ k )
        for (int i = n-1; i >= 0; -- i )
            Normal_Hash[k][i] = ((s[i]-'a') + 1LL * Normal_Hash[k][i+1] * Power_Base[Max_Pow-k]) % MOD;
}

int query(int i, int k) {
    int normal = (Normal_Hash[k][i] - (1LL * Normal_Hash[k][i+(1<<k)] * Power_Base[Max_Pow] % MOD) + MOD) % MOD;
    int brperm = BrPerm_Hash[k][i];

    if (normal == brperm) return 1;
    else return 0;
}

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