Submission #1188366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188366		pcheloveks	Brperm (RMI20_brperm)	C++20	100 / 100	550 ms	162708 KiB

brperm

#include "brperm.h"

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <climits>
#include <queue>
#include <algorithm>
#include <stdint.h>
#include <stack>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <cstring> // Для memset


using namespace std;
int n;
const long long MOD = 1e9 + 9;
long long p[530005], invp[530005];
long long put(long long a, long long exp)
{
    if (exp == 0)
        return 1;
    if (exp % 2 == 0)
        return put(a * a % MOD, exp / 2);
    else
        return put(a * a % MOD, exp / 2) * a % MOD;
}
int rev(int x, int k)
{
    int aux = 0;
    for (int i = 0; i < k; i++)
        if (((1 << i) & x))
            aux += (1 << (k - i - 1));
    return aux;
}
long long hsh[500005][19];
long long normal[500005][19];
long long sump[500005];
void init(int copn, const char s[])
{
    n = copn;
    p[0] = 1;
    p[1] = 31;
    for (int i = 2; i <= (1 << 19); i++)
        p[i] = (p[i - 1] * p[1]) % MOD;
    for (int i = 0; i <= (1 << 19); i++)
        invp[i] = put(p[i], MOD - 2);

    for (int i = 0; i < n; i++)
    {
        hsh[i][0] = normal[i][0] = s[i];
    }
    for (int k = 1; k < 19; k++)
    {
        for (int i = 0; i + (1 << k) - 1 < n; i++)
        {
            hsh[i][k] = (hsh[i][k - 1] + hsh[i + (1 << (k - 1))][k - 1] * p[(1 << (18 - k))]) % MOD;

            //for(int j=0;j<(1<<k);j++) normal[i][k] = (normal[i][k] + s[i+j]*p[j*(1<<(18-k))])%MOD;

        }
        long long pref = 0;
        long long prod = 1;
        for (int i = 0; i < n; i++)
        {
            pref = (pref + 1LL * s[i] * prod) % MOD;
            sump[i] = pref;
            prod = prod * p[(1 << (18 - k))] % MOD;
        }
        prod = 1;
        for (int i = 0; i + (1 << k) - 1 < n; i++)
        {
            normal[i][k] = sump[i + (1 << k) - 1];
            if (i > 0) normal[i][k] = (normal[i][k] + MOD - sump[i - 1]) % MOD;
            normal[i][k] = normal[i][k] * prod % MOD;
            prod = prod * invp[(1 << (18 - k))] % MOD;
        }
    }
}

int query(int i, int k)
{
    if (i + (1 << k) - 1 >= n)
        return 0;
    return hsh[i][k] == normal[i][k];
}

• Subtask 1: 13 / 13
• Subtask 2: 37 / 37
• Subtask 3: 17 / 17
• Subtask 4: 33 / 33