oj.uz

Submission #495480

# Submission time Handle Problem Language Result Execution time Memory
495480 2021-12-18T20:05:34 Z couplefire Brperm (RMI20_brperm) C++17
100 / 100
 305 ms 81424 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 712 KB Output is correct
2 Correct 2 ms 720 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 712 KB Output is correct
2 Correct 2 ms 720 KB Output is correct
3 Correct 53 ms 15724 KB Output is correct
4 Correct 66 ms 15688 KB Output is correct
5 Correct 59 ms 15692 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 81424 KB Output is correct
2 Correct 280 ms 81096 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 712 KB Output is correct
2 Correct 2 ms 720 KB Output is correct
3 Correct 53 ms 15724 KB Output is correct
4 Correct 66 ms 15688 KB Output is correct
5 Correct 59 ms 15692 KB Output is correct
6 Correct 301 ms 81424 KB Output is correct
7 Correct 280 ms 81096 KB Output is correct
8 Correct 290 ms 81076 KB Output is correct
9 Correct 291 ms 81096 KB Output is correct
10 Correct 305 ms 80988 KB Output is correct