Submission #1019914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019914		andrei_iorgulescu	Palindromes (APIO14_palindrome)	C++14	47 / 100	1071 ms	21396 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n;
char a[300005];

int modulo = 1e9 + 321;
int base = 59;
int powbase[300005],invpowbase[300005];
int h[300005],revh[300005];///sum din a[i] * B^(i - 1)

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

vector<double> ev[300005];///cu + daca il bag, - daca il scot

bool pal(int l,int r)
{
    if (l < 1 or r > n or l > r)
        return false;
    for (int i = l; i <= r; i++)
        if (a[i] != a[r + l - i])
            return false;
    return true;
    int h1 = (h[r] - h[l - 1] + modulo) % modulo * invpowbase[l - 1] % modulo;
    int h2 = (revh[l] - revh[r + 1] + modulo) % modulo * invpowbase[n - r] % modulo;
    if (h1 == h2)
        return true;
    return false;
}

int get_hash(int l, int r)
{
    int h1 = (h[r] - h[l - 1] + modulo) % modulo * invpowbase[l - 1] % modulo;
    return h1;
}

int lft[300005];
map<int,int> id;
pair<int,int> what[300005];///sa stiu si eu cam cum arata un string de acel id
int cnt_id;
int f[300005];
int l2[300005];

signed main()
{
    string when_what_where_how_why;
    cin >> when_what_where_how_why;
    n = when_what_where_how_why.size();
    for (int i = 1; i <= n; i++)
        a[i] = when_what_where_how_why[i - 1];
    powbase[0] = invpowbase[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        powbase[i] = base * powbase[i - 1] % modulo;
        if (i >= 2)
            invpowbase[i] = invpowbase[1] * invpowbase[i - 1] % modulo;
        else
            invpowbase[i] = lgpow(base,modulo - 2);
    }
    for (int i = 1; i <= n; i++)
        h[i] = (h[i - 1] + (a[i] - 'a' + 1) * powbase[i - 1]) % modulo;
    for (int i = n; i >= 1; i--)
        revh[i] = (revh[i + 1] + (a[i] - 'a' + 1) * powbase[n - i]) % modulo;
    for (int i = 1; i <= n; i++)
    {
        int st = 0,pas = 1 << 18;
        while (pas != 0)
        {
            if (pal(i - st - pas,i + st + pas))
                st += pas;
            pas /= 2;
        }
        ev[i].push_back(i);
        ev[i + st + 1].push_back(-i);
    }
    for (int i = 1; i < n; i++)
    {
        int st = 0,pas = 1 << 18;
        while (pas != 0)
        {
            if (pal(i - st - pas + 1,i + st + pas))
                st += pas;
            pas /= 2;
        }
        if (st == 0)
            continue;
        double lol = (double)i + 0.5d;
        ev[i + 1].push_back(lol);
        ev[i + st + 1].push_back(-lol);
    }
    multiset<double> ms;
    for (int i = 1; i <= n; i++)
    {
        for (auto it : ev[i])
        {
            double vl = it;
            if (vl > 0)
                ms.insert(vl);
            else
                ms.erase(ms.find(-vl));
        }
        double hmm = *ms.begin();
        double d = (double)i - hmm;
        d *= (2.0d);
        lft[i] = i - d;
        if (ms.size() == 1)
            continue;
        ms.erase(ms.find(hmm));
        double hmm2 = *ms.begin();
        d = (double)i - hmm2;
        d *= (2.0d);
        l2[i] = i - d;
        ms.insert(hmm);
    }
    for (int i = 1; i <= n; i++)
    {
        int cur = get_hash(lft[i],i);
        if (!id[cur])
            id[cur] = ++cnt_id;
        what[id[cur]] = {lft[i],i};
        f[id[cur]]++;
    }
    vector<pair<int,int>> ord;
    for (int i = 1; i <= cnt_id; i++)
        ord.push_back({what[i].second - what[i].first + 1,i});
    sort(ord.begin(),ord.end());
    reverse(ord.begin(),ord.end());
    int ans = 0;
    for (auto it : ord)
    {
        ans = max(ans,it.first * f[it.second]);
        if (it.first == 1)
            continue;
        int cn = what[it.second].second;
        int h2 = get_hash(l2[cn],cn);
        int id2 = id[h2];
        f[id2] += f[it.second];
    }
    cout << ans;
    return 0;
}

/**
Maxim N palindroame distincte etc
Voi vrea pentru fiecare sa retin frecventa lui
Pentru asta, merg cu i de la 1 la N, iau cel mai mare palindrom care se termina pe i
Ii gasesc id-ul (ori un id nou ori ceva id vechi fiindca deja exista)
Acum, vreau sa adaug 1 pe toate palindroamele care se termina pe i <=> toate sufixele palindrom ale lui pal[id] <=> toate prefixele palindrom
Dau f[id]++

La final, vreau sa propag f-urile pe toate prefixele palindrom
Foarte simplu, iau palindroamele descrescator dupa lungime, pentru asta o sa am f[id] updatat si il consider la raspuns
Fie pal[id'] = prefixul maxim palindrom al lui pal[id] (daca pal[id] are lungime 1, ma opresc)
Dau f[id'] += f[id] and we move on
**/

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27