oj.uz

Submission #1013539

# Submission time Handle Problem Language Result Execution time Memory
1013539 2024-07-03T15:51:12 Z andrei_iorgulescu Brperm (RMI20_brperm) C++14
100 / 100
 558 ms 104784 KB 
#include "brperm.h"
#include <bits/stdc++.h>

using namespace std;

using integer = int;

#define int long long

int n;
char a[500005];
int h[20][500005];///hashul pentru prefix de 2^p din sirul gen 0,8,4,12,2,10,6,14
bool ans[20][500005];///pentru k = i, p = j
int pref_h[500005];

int base = 37;
int modulo = 1e9 + 123;

int powbase[500005],invpowbase[500005];

int lgpow(int x,int y)
{
    int z = 1;
    while (y != 0)
    {
        if (y % 2 == 1)
            z = 1ll * z * x % modulo;
        x = 1ll * x * x % modulo;
        y /= 2;
    }
    return z;
}

void init(integer N, const char S[])
{
    powbase[0] = invpowbase[0] = 1;
    for (int i = 1; i <= 500000; i++)
    {
        powbase[i] = 1ll * powbase[i - 1] * base % modulo;
        invpowbase[i] = lgpow(powbase[i],modulo - 2);
    }
    n = N;
    for (int i = 1; i <= n; i++)
        a[i] = S[i - 1];
    for (int i = 1; i <= n; i++)
        ans[0][i] = true;
    for (int k = 1; k <= 18; k++)
    {
        memset(h,0,sizeof(h));
        memset(pref_h,0,sizeof(pref_h));
        for (int i = 1; i <= n; i++)
            h[0][i] = (a[i] - 'a' + 1);
        for (int j = 1; j <= k; j++)
            for (int i = 1; i + (1 << k) - (1 << (k - j)) <= n; i++)
                h[j][i] = ((long long)h[j - 1][i] + 1ll * powbase[(1 << (j - 1))] * h[j - 1][i + (1 << (k - j))]) % modulo;
        for (int i = 1; i <= n; i++)
            pref_h[i] = ((long long)pref_h[i - 1] + 1ll * powbase[i - 1] * (a[i] - 'a' + 1)) % modulo;
        for (int i = 1; i <= n - (1 << k) + 1; i++)
        {
            int hh = (modulo + pref_h[i + (1 << k) - 1] - pref_h[i - 1]) % modulo;
            hh = 1ll * hh * invpowbase[i - 1] % modulo;
            //cout << i << ' ' << hh << ' ' << h[k][i] << endl;
            if (hh == h[k][i])
                ans[k][i] = true;
        }
    }
}

integer query(integer i,integer k)
{
    i++;
    if (ans[k][i])
        return (integer)1;
    return (integer)0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 90412 KB Output is correct
2 Correct 148 ms 90464 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 90412 KB Output is correct
2 Correct 148 ms 90464 KB Output is correct
3 Correct 196 ms 92172 KB Output is correct
4 Correct 185 ms 92248 KB Output is correct
5 Correct 195 ms 92132 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 104784 KB Output is correct
2 Correct 515 ms 101596 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 90412 KB Output is correct
2 Correct 148 ms 90464 KB Output is correct
3 Correct 196 ms 92172 KB Output is correct
4 Correct 185 ms 92248 KB Output is correct
5 Correct 195 ms 92132 KB Output is correct
6 Correct 514 ms 104784 KB Output is correct
7 Correct 515 ms 101596 KB Output is correct
8 Correct 558 ms 99408 KB Output is correct
9 Correct 499 ms 99460 KB Output is correct
10 Correct 537 ms 99456 KB Output is correct