Submission #677869

#	Time	Username	Problem	Language	Result	Execution time	Memory
677869		Romiros	회문 (APIO14_palindrome)	C++17	15 / 100	1092 ms	13164 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];
}

vector<int> build_sa(string s){
    int n = s.size();
    vector<int> a(n);
    vector<int> eq(2 * n + 1);
    vector<int> nw(2 * n + 1);
    vector<int> t(n + 1);
    vector<int> nw_a(n);
    for (int i = 0; i < n; i++){
        a[i] = i;
    }
    sort(a.begin(), a.end(), [&](int x, int y){
        return s[x] < s[y] || (s[x] == s[y] && x < y);
    });
    eq[a[0]] = 1;
    for (int i = 1; i < n; i++){
        eq[a[i]] = eq[a[i - 1]] + (s[a[i]] != s[a[i - 1]]);
    }
    for (int k = 0; (1 << k) <= n; k++){
        for (int f = 1; f >= 0; f--){
            t.assign(n + 1, 0);
            for (int i = 0; i < n; i++){
                int j = a[i] + (f << k);
                t[eq[j]]++;
            }
            for (int i = 1; i <= n; i++){
                t[i] += t[i - 1];
            }
            for (int i = n; i >= 1; i--){
                t[i] = t[i - 1];
            }
            t[0] = 0;
            for (int i = 0; i < n; i++){
                int j = a[i] + (f << k);
                nw_a[t[eq[j]]++] = a[i];
            }
            nw_a.swap(a);
        }
        nw[a[0]] = 1;
        for (int i = 1; i < n; i++){
            int p = a[i];
            int q = a[i - 1];
            nw[p] = nw[q];
            if (eq[p] != eq[q] || eq[p + (1 << k)] != eq[q + (1 << k)]){
                nw[p]++;
            }
        }
        nw.swap(eq);
    }
    a.insert(a.begin(), n);
    return a;
}
 
vector<int> build_lcp(const vector<int>& p, const string& s){
    int n = s.size();
    vector<int> pos(n + 1);
    for (int i = 0; i <= n; i++){
        pos[p[i]] = i;
    }
    vector<int> lcp(n);
    int k = 0;
    for (int i = 0; i < (n - 1); i++){
        while (s[i + k] == s[p[pos[i] - 1] + k]){
            k++;
        }
        lcp[pos[i] - 1] = k;
        k -= (k != 0);
    }
    return lcp;
}

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();   
        vector<int> sa = build_sa(s);
        vector<int> lcp = build_lcp(sa, s);
        for (int i = 1; i <= n; i++){
            sa[i]++;
        }
        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 = sa;
            // 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 = 1; 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, min({lcp[j], d[order[j]], d[order[j + 1]]}));
                    }
                }
            }
        }
        cout << res << "\n";
    }
    return 0;
}

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