Submission #1034693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034693		andrei_iorgulescu	Brperm (RMI20_brperm)	C++14	100 / 100	396 ms	59732 KiB

brperm

#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 / 13
• Subtask 2: 37 / 37
• Subtask 3: 17 / 17
• Subtask 4: 33 / 33