oj.uz

Submission #1034693

# Submission time Handle Problem Language Result Execution time Memory
1034693 2024-07-25T16:48:22 Z andrei_iorgulescu Brperm (RMI20_brperm) C++14
100 / 100
 396 ms 59732 KB 
#include "brperm.h"
#include <bits/stdc++.h>
 
using namespace std;
 
using integer = int;
 
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;
		if (i == 1)
        	invpowbase[i] = lgpow(powbase[i],modulo - 2);
		else
			invpowbase[i] = 1ll * invpowbase[1] * invpowbase[i - 1] % modulo;
    }
    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 43 ms 45404 KB Output is correct
2 Correct 47 ms 45404 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 45404 KB Output is correct
2 Correct 47 ms 45404 KB Output is correct
3 Correct 107 ms 47184 KB Output is correct
4 Correct 106 ms 47088 KB Output is correct
5 Correct 104 ms 47184 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 59732 KB Output is correct
2 Correct 382 ms 56400 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 45404 KB Output is correct
2 Correct 47 ms 45404 KB Output is correct
3 Correct 107 ms 47184 KB Output is correct
4 Correct 106 ms 47088 KB Output is correct
5 Correct 104 ms 47184 KB Output is correct
6 Correct 390 ms 59732 KB Output is correct
7 Correct 382 ms 56400 KB Output is correct
8 Correct 396 ms 54612 KB Output is correct
9 Correct 379 ms 54352 KB Output is correct
10 Correct 381 ms 54456 KB Output is correct