Submission #105057

#	Time	Username	Problem	Language	Result	Execution time	Memory
105057		Akashi	Palindromes (APIO14_palindrome)	C++14	73 / 100	1083 ms	75492 KiB

palindrome

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

//struct usu{
//    int x, y, p;
//    bool operator < (const usu &aux)const{
//        if(x != aux.x) return x < aux.x;
//        if(y != aux.y) return y < aux.y;
//        return p < aux.p;
//    }
//};
//usu L[300005];

int n, lgn;
int cnt[300005];
char s[300005], T[600005];
int P[20][300005], C[20][300005], RMQ[20][300005];
int LP[600005];
int lg[300005], SA[300005], EC[300005];

//void build_suffix_array(){
//    for(int i = 1; i <= n ; ++i) C[0][i] = s[i] - 'a' + 1;
//
//    for(int k = 1; k <= lgn ; ++k){
//        int put = (1 << (k - 1));
//        for(int i = 1; i <= n ; ++i)
//            L[i] = {C[k - 1][i], ((i + put) <= n) ? C[k - 1][i + put] : -1, i};
//
//        sort(L + 1, L + n + 1);
//        C[k][L[1].p] = 1;
//        for(int i = 2; i <= n ; ++i){
//            if(L[i].x == L[i - 1].x && L[i].y == L[i - 1].y) C[k][L[i].p] = C[k][L[i - 1].p];
//            else C[k][L[i].p] = i;
//        }
//        if(k == lgn){
//            int NR = 0;
//            SA[++NR] = L[1].p;
//            for(int i = 2; i <= n ; ++i) SA[++NR] = L[i].p;
//        }
//    }
//}
void build_suffix_array(){
    ///P the sorted array of the positions
    ///C the equivalence class

    for(int i = 1; i <= n ; ++i) ++cnt[s[i] - 'a'];
    for(int i = 1; i < 26 ; ++i) cnt[i] += cnt[i - 1];
    for(int i = 1; i <= n ; ++i) P[0][cnt[s[i] - 'a']--] = i;

    C[0][P[0][1]] = 1;
    int NR = 1;
    cnt[1] = cnt[0] = 0;
    for(int i = 2; i <= n ; ++i){
        if(s[P[0][i]] != s[P[0][i - 1]]) ++NR, cnt[NR] = 0;
        C[0][P[0][i]] = NR;
    }

    for(int k = 1; k <= lgn ; ++k){
        int put = (1 << (k - 1));

        for(int i = 1; i <= n ; ++i){
            if(i + put <= n) EC[i] = C[k - 1][i + put];
            else EC[i] = 0;
            ++cnt[EC[i]];
        }

        for(int i = 1; i <= NR ; ++i) cnt[i] += cnt[i - 1];
        for(int i = n; i >= 1 ; --i) SA[cnt[EC[i]]--] = i;

        memset(cnt, 0, sizeof(cnt));

        for(int i = 1; i <= n ; ++i) ++cnt[C[k - 1][i]];
        for(int i = 1; i <= NR ; ++i) cnt[i] += cnt[i - 1];
        for(int i = 1; i <= n ; ++i) P[k][cnt[C[k - 1][SA[i]]]--] = SA[i];

        C[k][P[k][1]] = 1;
        NR = 1;
        cnt[1] = cnt[0] = 0;
        pair <int, int> p1, p2;
        p2.first = C[k - 1][P[k][1]];
        if(P[k][1] + put <= n) p2.second = C[k - 1][P[k][1] + put];
        else p2.second = -1;
        for(int i = 2; i <= n ; ++i){
            p1.first = C[k - 1][P[k][i]];
            if(P[k][i] + put <= n) p1.second = C[k - 1][P[k][i] + put];
            else p1.second = -1;

            if(p1 != p2) ++NR, cnt[NR] = 0;
            p2 = p1;
            C[k][P[k][i]] = NR;
        }
    }
    for(int i = 1; i <= n ; ++i) SA[i] = P[lgn][i];
}

inline int find_lcp(int x, int y){
    int ans = 0;
    for(int k = lgn; k >= 0 ; --k){
        if(max(x + ans, y + ans) > n) continue ;
        if(C[k][x + ans] == C[k][y + ans]) ans += (1 << k);
    }
    return ans;
}

void build_lcp(){
    for(int i = 1; i < n ; ++i) RMQ[0][i] = find_lcp(SA[i], SA[i + 1]);

    for(int k = 1; k <= lgn ; ++k){
        int put = (1 << (k - 1)), put2 = (1 << k);
        for(int i = 1; i <= n - put2 ; ++i) RMQ[k][i] = min(RMQ[k - 1][i], RMQ[k - 1][i + put]);
    }
}
inline int use_lcp(int x, int y){
    if(x == y) return n - x + 1;

    x = C[lgn][x], y = C[lgn][y];
    if(x > y) swap(x, y);

    int l = y - x, k = lg[l];
    return min(RMQ[k][x], RMQ[k][y - (1 << k)]);
}
inline int nrap(int x, int y){
    int st = 1, dr = C[lgn][x] - 1, Sol1 = 0, Sol2 = 0;
    while(st <= dr){
        int mij = (st + dr) >> 1;
        if(use_lcp(x, SA[mij]) >= y - x + 1){
            Sol1 = C[lgn][x] - mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }

    st = C[lgn][x] + 1, dr = n;
    while(st <= dr){
        int mij = (st + dr) >> 1;
        if(use_lcp(x, SA[mij]) >= y - x + 1){
            Sol2 = mij - C[lgn][x];
            st = mij + 1;
        }
        else dr = mij - 1;
    }
    return Sol1 + Sol2 + 1;
}
int main()
{
//    freopen("palindrome.in", "r", stdin);
//    freopen("palindrome.out", "w", stdout);

    lg[1] = 0;
    for(int i = 2; i <= 300000 ; ++i) lg[i] = lg[i >> 1] + 1;

    scanf("%s", s + 1);
    n = strlen(s + 1);
    lgn = log2(n) + 1;

    build_suffix_array();
    build_lcp();

    ///manacher-sama
    int NR = 0;
    T[++NR] = '.';
    for(int i = 1; i <= n ; ++i) T[++NR] = s[i], T[++NR] = '.';

    int R = 0, C = 0;
    long long Sol = 0;
    for(int i = 1; i <= NR ; ++i){
        int rad = 0;
        if(i <= R) rad = min(R - i, LP[2 * C - i]) + 1;

        while(i + rad < NR && i - rad > 0 && T[i + rad] == T[i - rad]){
            if(((i + rad) & 1) == 0) Sol = max(Sol, 1LL * (rad + 1) * nrap((i - rad) >> 1, (i + rad) >> 1));
            ++rad;
        }
        LP[i] = rad - 1;
        if(i + rad - 1 > R){
            R = i + rad - 1;
            C = i;
        }
    }
    printf("%lld", Sol);

    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:155:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s + 1);
     ~~~~~^~~~~~~~~~~~~

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