oj.uz

Submission #478273

# Submission time Handle Problem Language Result Execution time Memory
478273 2021-10-06T19:04:21 Z stefantaga Brperm (RMI20_brperm) C++14
100 / 100
 329 ms 81096 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 66 ms 14920 KB Output is correct
4 Correct 58 ms 14788 KB Output is correct
5 Correct 60 ms 14868 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 80564 KB Output is correct
2 Correct 329 ms 81004 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 66 ms 14920 KB Output is correct
4 Correct 58 ms 14788 KB Output is correct
5 Correct 60 ms 14868 KB Output is correct
6 Correct 322 ms 80564 KB Output is correct
7 Correct 329 ms 81004 KB Output is correct
8 Correct 309 ms 81064 KB Output is correct
9 Correct 314 ms 81004 KB Output is correct
10 Correct 312 ms 81096 KB Output is correct