Submission #677864

#	Time	Username	Problem	Language	Result	Execution time	Memory
677864		Romiros	Palindromes (APIO14_palindrome)	C++17	23 / 100	1091 ms	10548 KiB

palindrome

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define vi vector<int>
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ull unsigned long long

using namespace std;

const int MAXN = 3e5 + 10;

ull pw[MAXN + 10];
ull pref[MAXN];
ull suff[MAXN];
int n;

ull h(int i, int j){
    return (pref[j] - pref[i - 1]) * pw[MAXN - i + 1];
}

ull rh(int i, int j){
    return (suff[i] - suff[j + 1]) * pw[MAXN + j - n];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifdef ON_PC
        freopen("input.txt", "r", stdin);
    #endif
    // freopen("output.txt", "w", stdout);
    pw[0] = 1;
    for (int i = 1; i < MAXN + 10; i++){
        pw[i] = pw[i - 1] * 57;
    }
    int T = 1;
    // cin >> T;
    while (T--){
        string s;
        cin >> s;
        n = s.size();   
        s = " " + s;
        for (int i = 1; i <= n; i++){
            pref[i] = pref[i - 1] + (s[i] - 'a' + 1) * pw[i - 1];
        }
        for (int i = n; i >= 1; i--){
            suff[i] = suff[i + 1] + (s[i] - 'a' + 1) * pw[n - i];
        }
        ll res = 0;
        for (int f = 0; f < 2; f++){
            vector<int> d(n + 1);
            for (int i = 1; i <= n; i++){
                int l = 0, r = min(i, n - (i + f) + 1) + 1;
                while (r - l > 1){
                    int m = (l + r) / 2;
                    if (rh(i - m + 1, i) == h(i + f, i + f + m - 1)){
                        l = m;
                    } else {
                        r = m;
                    }
                }
                d[i] = l;
            }
            vector<int> order(n);
            for (int i = 1; i <= n; i++){
                order[i - 1] = i;
            }
            function<int(int, int)> lcp = [&](int i, int j){
                int l = 0, r = min(d[i], d[j]) + 1;
                while (r - l > 1){
                    int m = (l + r) / 2;
                    if (h(i - m + 1, i) == h(j - m + 1, j)){
                        l = m;
                    } else {
                        r = m;
                    }
                }
                return l;
            };
            sort(all(order), [&](int i, int j){
                int l = lcp(i, j);
                if (l == min(d[i], d[j])){
                    if (d[i] != d[j]){
                        return d[i] < d[j];
                    }
                    return i < j;
                }
                return s[i - l] < s[j - l];
            });
            for (int i = 0; i < n; i++){
                int mn = d[order[i]];
                for (int j = i; j < n; j++){
                    res = max(res, (j - i + 1) * 1ll * (2 * mn - !f));
                    if (j + 1 < n){
                        mn = min(mn, lcp(order[j], order[j + 1]));
                    }
                }
            }
        }
        cout << res << "\n";
    }
    return 0;
}

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