Submission #365463

#	Time	Username	Problem	Language	Result	Execution time	Memory
365463		BartolM	Palindromes (APIO14_palindrome)	C++17	73 / 100	1041 ms	66884 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 rmq[LOG][N];

int ind[N], novi[N];
vector <int> vec[N];
#define DEBUG 0
int counter[30];

int cmp(int a, int b) {
    return s[a]<s[b];
}

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 build_rmq() {
    for (int i=0; i<n; ++i) rmq[0][i]=lcp[i];
    for (int i=1; i<LOG; ++i) {
        for (int j=0; j<n; ++j) {
            rmq[i][j]=rmq[i-1][j];
            if (j+(1<<i)<=n) rmq[i][j]=min(rmq[i][j], rmq[i-1][j+(1<<(i-1))]);
        }
    }
}

int broj(int pos, int d) {
    if (d==1) return counter[s[pos]-'a'];

    int l=ind[pos]-1, r=ind[pos];

    int res=0;
    int x=(1<<(LOG-1));
    for (int i=LOG-1; i>=0; --i) {
        if (r+x<=n && rmq[i][r]>=d) r+=x;
        if (l-x>=-1 && rmq[i][l-x+1]>=d) l-=x;
        x/=2;
    }
    return r-l;
}

void solve() {
    build_suff();
    build_lcp();
    build_rmq();
#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]]) {
            sol=max(sol, (ll)broj(i-odd[i], odd[i]*2+1)*(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]]) {
            sol=max(sol, (ll)broj(i-even[i]-1, even[i]*2+2)*(even[i]*2+2));
            even[i]++;
        }
        if (i+even[i]-1>r) cent=i, r=i+even[i]-1;
    }
    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 'int broj(int, int)':
palindrome.cpp:93:9: warning: unused variable 'res' [-Wunused-variable]
   93 |     int res=0;
      |         ^~~
palindrome.cpp: In function 'void load()':
palindrome.cpp:147:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  147 |     scanf("%s", s);
      |     ~~~~~^~~~~~~~~

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