Submission #364724

#	Time	Username	Problem	Language	Result	Execution time	Memory
364724		BartolM	Palindromes (APIO14_palindrome)	C++17	23 / 100	1099 ms	54524 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=19;

int n;
char s[N];
int suff[N], lcp[N];
int rmq[LOG][N];

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

string str; string pom;

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

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]=(suff[i]-j+n)%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[(suff[i-1]+j)%n]==ind[(suff[i]+j)%n]) 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) {
    int l=ind[pos]-1, r=ind[pos];

    int res=0;
    for (int i=LOG-1; i>=0; --i) {
        if (r+(1<<i)<=n && rmq[i][r]>=d) r+=(1<<i);
        if (l-(1<<i)>=-1 && rmq[i][l-(1<<i)+1]>=d) l-=(1<<i);
    }
    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 l=0; l<n-1; ++l) {
        for (int r=l; r<n-1; ++r) {
            pom=str;
            reverse(pom.begin()+l, pom.begin()+r+1);
            if (pom==str) sol=max(sol, (ll)(r-l+1)*broj(l, r-l+1));
        }
    }
    printf("%lld\n", sol);
}

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

    str=s; pom=s;
}

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

Compilation message (stderr)

palindrome.cpp: In function 'int broj(int, int)':
palindrome.cpp:87:9: warning: unused variable 'res' [-Wunused-variable]
   87 |     int res=0;
      |         ^~~
palindrome.cpp: In function 'void load()':
palindrome.cpp:120:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  120 |     scanf("%s", s);
      |     ~~~~~^~~~~~~~~

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