Submission #642122

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
642122	2022-09-18T14:47:13 Z	Tenis0206	Brperm (RMI20_brperm)	C++14	Compilation error	0 ms	0 KB

brperm

#include <bits/stdc++.h>
#define int long long

//#define home

#ifndef home

#include "brperm.h"

#endif // home

using namespace std;

const int Mod = 1e9;
const int b = 27;

int n;
char c[500005];

int put[500005];
int hr[500005][25];
int h[500005][25];

int lg = 0;

int lgput(int x, int y)
{
    int p = 1;
    while(y)
    {
        if(y % 2 == 0)
        {
            y /= 2;
            x = 1LL * x * x % Mod;
        }
        else
        {
            --y;
            p = 1LL * p * x % Mod;
        }
    }
    return p;
}

void build_hr()
{
    for(int i=1;i<=n;i++)
    {
        hr[i][0] = (c[i] - 'a' + 1);
    }
    for(int k=1;k<=lg;k++)
    {
        for(int i=1;i<=n;i++)
        {
            if(i + (1<<k) - 1 > n)
            {
                break;
            }
            hr[i][k] = 1LL * (put[(1<<(lg-k))] * hr[i][k-1] + hr[i + (1<<(k-1))][k-1]) % Mod;
        }
    }
}

void build_h()
{
    for(int k=0;k<=lg;k++)
    {
        for(int i=1;i<=n;i++)
        {
            h[i][k] = (h[i-1][k] * put[(1<<k)] + c[i] - 'a' + 1) % Mod;
        }
    }
}

int get_hash(int st, int k)
{
    int p = lg - k;
    int dr = st + (1<<k) - 1;
    return (h[dr][p] - h[st-1][p] * lgput(b, (1<<p) * (dr - st + 1)) % Mod + Mod) % Mod;
}

void init(int N, const char s[])
{
    n = N;
    put[0] = 1;
    for(int i=1;i<=n;i++)
    {
        put[i] = 1LL * put[i-1] * b % Mod;
    }
    for(int i=1;i<=n;i++)
    {
        c[i] = s[i-1];
    }
    int nr = 1;
    while(nr<=n)
    {
        ++lg;
        nr = 2 * nr;
    }
    --lg;
    build_hr();
    build_h();
}

int query(int poz, int k)
{
    ++poz;
    return (hr[poz][k]==get_hash(poz,k));
}

#ifdef home

int nn,qq;
char ss[500005];

signed main()
{
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    cin>>nn;
    for(int i=0;i<nn;i++)
    {
        cin>>ss[i];
    }
    init(nn,ss);
    cin>>qq;
    for(int i=1;i<=qq;i++)
    {
        int poz,k;
        cin>>poz>>k;
        cout<<query(poz,k)<<'\n';
    }
    return 0;
}

#endif // home

Compilation message

/usr/bin/ld: /tmp/ccbMPLTP.o: in function `main':
grader.cpp:(.text.startup+0x72): undefined reference to `init(int, char const*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x89): undefined reference to `query(int, int)'
collect2: error: ld returned 1 exit status