Submission #366590

#	Time	Username	Problem	Language	Result	Execution time	Memory
366590		BartolM	Palindromes (APIO14_palindrome)	C++17	73 / 100	1042 ms	58076 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=3e5+5;
const int LOG=20;

int n;
char s[N];
int suff[N], lcp[N];
int odd[N], even[N];
int ind[N], novi[N];

vector <int> vec[N];
int counter[30];
vector <pii> v, upd;
int P[N], siz[N], dub[N];

#define DEBUG 0
int cmp(int a, int b) {
    return s[a]<s[b];
}

int cmp2(pii a, pii b) {
    if (a.Y==b.Y) return a.X<b.X;
    return a.Y>b.Y;
}

int name(int x) {
    if (x==P[x]) return x;
    P[x]=name(P[x]);
    return P[x];
}

void mrg(int a, int b) {
    a=name(a); b=name(b);
    if (a==b) return;
    if (siz[a]>siz[b]) swap(a, b);
    P[a]=b;
    siz[b]+=siz[a];
//    dub[b]=max(dub[b], dub[a]+1);
}

inline int modaj(int x) {
    return x>=n ? x-n : x;
}

void build_suff() {
    s[n]='$'; s[n+1]='\0'; n++;
    for (int i=0; i<n; ++i) suff[i]=i;

    sort(suff, suff+n, cmp);
    ind[suff[0]]=0;
    for (int i=1; i<n; ++i) ind[suff[i]]=ind[suff[i-1]]+(s[suff[i]]!=s[suff[i-1]]);

    for (int j=1; j<n; j*=2) {
        for (int i=0; i<n; ++i) vec[i].clear();
        for (int i=0; i<n; ++i) {
            suff[i]=modaj(suff[i]-j+n);
            vec[ind[suff[i]]].pb(suff[i]);
        }

        int curr=0;
        for (int i=0; i<n; ++i)
            for (int x:vec[i])
                suff[curr++]=x;

        novi[suff[0]]=0;
        for (int i=1; i<n; ++i) {
            if (ind[suff[i-1]]==ind[suff[i]] && ind[modaj(suff[i-1]+j)]==ind[modaj(suff[i]+j)]) novi[suff[i]]=novi[suff[i-1]];
            else novi[suff[i]]=novi[suff[i-1]]+1;
        }
        memcpy(ind, novi, sizeof(novi));
    }
}

void build_lcp() {
    int lc=0;
    for (int i=0; i<n-1; ++i) {
        int curr=ind[i];
        int j=suff[curr-1];
        while (s[i+lc]==s[j+lc]) lc++;
        lcp[curr-1]=lc;
        lc=max(lc-1, 0);
    }
}

void sortiraj(vector <pii> &A) {
    for (int i=0; i<=n; ++i) vec[i].clear();
    for (pii pp:A) vec[pp.Y].pb(pp.X);

    A.clear();
    for (int i=n; i>=0; --i)
        for (int x:vec[i])
            A.pb(mp(x, i));

}

void solve() {
    build_suff();
    build_lcp();
#if DEBUG

    for (int i=0; i<n; ++i) printf("%d ", suff[i]);
    printf("\n");
    for (int i=0; i<n; ++i) printf("%d ", lcp[i]);
    printf("\n");

#endif // DEBUG

    ll sol=0;
    for (int i=0; i<n-1; ++i) counter[s[i]-'a']++;
    for (int i=0; i<26; ++i) sol=max(sol, (ll)counter[i]);

    odd[0]=1;
    int cent=0, r=0;
    for (int i=1; i<n-1; ++i) {

        odd[i]=(i>r) ? 1 : min(r-i+1, odd[cent-(i-cent)]);
        while (i-odd[i]>=0 && i+odd[i]<n && s[i-odd[i]]==s[i+odd[i]]) {
            v.pb(mp(i-odd[i], odd[i]*2+1));
            odd[i]++;
        }
        if (i+odd[i]-1>r) cent=i, r=i+odd[i]-1;
    }

    even[0]=0;
    cent=0, r=0;
    for (int i=1; i<n-1; ++i) {
        even[i]=(i>r) ? 0 : min(r-i+1, even[cent-(i-cent)-1]);
        while (i-even[i]-1>=0 && i+even[i]<n && s[i-even[i]-1]==s[i+even[i]]) {
            v.pb(mp(i-even[i]-1, even[i]*2+2));
            even[i]++;
        }
        if (i+even[i]-1>r) cent=i, r=i+even[i]-1;
    }
    for (int i=1; i<n-1; ++i) upd.pb(mp(i, lcp[i]));

    sortiraj(upd);
    sortiraj(v);

    for (int i=0; i<n; ++i) P[i]=i, siz[i]=1;

    int j=0;
    for (int i=0; i<v.size(); ++i) {
        while (j<upd.size() && upd[j].Y>=v[i].Y) {
//            printf("update %d i %d\n", suff[upd[j].X], suff[upd[j].X+1]);
            mrg(suff[upd[j].X], suff[upd[j].X+1]);
            j++;
        }
//        printf("pos: %d, dulj: %d\n", v[i].X, v[i].Y);
        int x=name(v[i].X);
        sol=max(sol, (ll)v[i].Y*siz[x]);
    }
    printf("%lld\n", sol);
}

void load() {
    scanf("%s", s);
    n=strlen(s);

}

int main() {
    load();
    solve();
    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'void solve()':
palindrome.cpp:156:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |     for (int i=0; i<v.size(); ++i) {
      |                   ~^~~~~~~~~
palindrome.cpp:157:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |         while (j<upd.size() && upd[j].Y>=v[i].Y) {
      |                ~^~~~~~~~~~~
palindrome.cpp: In function 'void load()':
palindrome.cpp:170:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  170 |     scanf("%s", s);
      |     ~~~~~^~~~~~~~~

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