oj.uz

Submission #474475

# Submission time Handle Problem Language Result Execution time Memory
474475 2021-09-18T12:09:44 Z Alexandruabcde Brperm (RMI20_brperm) C++14
100 / 100
 344 ms 81324 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 64 ms 15720 KB Output is correct
4 Correct 72 ms 15660 KB Output is correct
5 Correct 66 ms 15684 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 81324 KB Output is correct
2 Correct 344 ms 81076 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 64 ms 15720 KB Output is correct
4 Correct 72 ms 15660 KB Output is correct
5 Correct 66 ms 15684 KB Output is correct
6 Correct 343 ms 81324 KB Output is correct
7 Correct 344 ms 81076 KB Output is correct
8 Correct 342 ms 81164 KB Output is correct
9 Correct 344 ms 81092 KB Output is correct
10 Correct 335 ms 81092 KB Output is correct