Submission #23261

#	Time	Username	Problem	Language	Result	Execution time	Memory
23261		Nurlykhan	Palindromes (APIO14_palindrome)	C++14	0 / 100	1000 ms	14892 KiB

palindrome

#include <bits/stdc++.h>

#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long 
#define ld long double
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()

using namespace std;

const int N = (int) 3e5 + 10;
const int M = (int) 2e6 + 10;
const ll LINF = (ll) 1e18;
const int INF = (int) 1e9 + 7;
const double EPS = (double) 1e-9;
string st;
ll ans;
int h[N], h1[N];
int p[N];

int get_hash(int l, int r) {
    int ans = (h[r] - (l ? h[l - 1] : 0) + INF) % INF;
    ans = ans * 1ll * p[sz(st) - 1 - r] % INF;
    return ans;
}

int get_revhash(int l, int r) {
    int ans = (h1[l] - h1[r + 1] + INF) % INF;
    ans = ans * 1ll * p[l] % INF;
    return ans;
}

int first_diff(pii x, pii y) {
    int l = 0, r = min(x.s - x.f, y.s - y.f);
    int neq = -1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (get_hash(x.f, x.f + m) == get_hash(y.f, y.f + m)) {
            l = m + 1;
        } else {
            neq = m;
            r = m - 1;
        }
    }
    return neq;
}

bool cmp(pii x, pii y) {
    int neq = first_diff(x, y);
    if (neq == -1) 
        return x.s - x.f < y.s - y.f;
    return st[x.f + neq] < st[y.f + neq];
}

vector<int> get_shit1(vector<int> v) {
    vector<int> st, ret(sz(v));
    for (int i = 0; i < sz(v); i++) {
        while (!st.empty() && v[i] <= v[st.back()]) st.pop_back();
        ret[i] = st.empty() ? 0 : st.back() + 1;
        st.pb(i);
    }
    return ret;
}

vector<int> get_shit2(vector<int> v) {
    vector<int> st, ret(sz(v));
    for (int i = sz(v) - 1; i >= 0; i--) {
        while (!st.empty() && v[i] <= v[st.back()]) st.pop_back();
        ret[i] = st.empty() ? sz(v) - 1 : st.back() - 1;
        st.pb(i);
    }
    return ret;
}

void solve_odd() {
    vector<pii> v;
    for (int i = 0; i < sz(st); i++) {
        int l = 0, r = sz(st);
        int j = 0;
        while (l <= r) {
            int m = (l + r) / 2;
            if (i - m >= 0 && i + m < sz(st) && get_hash(i, i + m) == get_revhash(i - m, i)) {
                l = m + 1;
                j = m;
            } else {
                r = m - 1;
            }
        }
        v.pb(mp(i, i + j));
    }
    sort(all(v), cmp);
    //for (auto it : v) cout << it << endl; cout << "-----\n";
    vector<int> lcp(sz(v) - 1);
    for (int i = 0; i + 1 < sz(v); i++) {
        lcp[i] = first_diff(v[i], v[i + 1]);
        if (lcp[i] == -1) 
            lcp[i] = min(v[i].s - v[i].f, v[i + 1].s - v[i + 1].f) + 1;
    }
    for (int i = 0; i < sz(v); i++) {
        ans = max(ans, 2ll * (v[i].s - v[i].f + 1) - 1);
    }
    vector<int> tmp1 = get_shit1(lcp);
    vector<int> tmp2 = get_shit2(lcp);
    for (int i = 0; i < sz(lcp); i++) {
        int occurs = tmp1[i] - i + tmp2[i] - i + 1;
        ans = max(ans, (occurs + 1) * 1ll * (lcp[i] * 2 - 1));
    }
}


void solve_even() {
    vector<pii> v;
    for (int i = 0; i < sz(st); i++) {
        int l = 0, r = sz(st);
        int j = -1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (i - 1 - m >= 0 && i + m < sz(st) && get_hash(i, i + m) == get_revhash(i - 1 - m, i - 1)) {
                l = m + 1;
                j = m;
            } else {
                r = m - 1;
            }
        }
        if (j != -1) v.pb(mp(i, i + j));
    }
    if (v.empty()) return;
    sort(all(v), cmp);
    vector<int> lcp(sz(v) - 1);
    //for (auto it : v) cout << it << endl; cout << "-----\n";
    for (int i = 0; i + 1 < sz(v); i++) {
        lcp[i] = first_diff(v[i], v[i + 1]);
        if (lcp[i] == -1) 
            lcp[i] = min(v[i].s - v[i].f, v[i + 1].s - v[i + 1].f) + 1;
    }
    for (int i = 0; i < sz(v); i++) {
        ans = max(ans, 2ll * (v[i].s - v[i].f + 1));
    }
    vector<int> tmp1 = get_shit1(lcp);
    vector<int> tmp2 = get_shit2(lcp);
    for (int i = 0; i < sz(lcp); i++) {
        int occurs = tmp1[i] - i + tmp2[i] - i + 1;
        ans = max(ans, (occurs + 1) * 2ll * lcp[i]);
    }
}

int main() {
    #define fn "balls"
    #ifdef witch
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
//        freopen(fn".in", "r", stdin);
//        freopen(fn".out", "w", stdout);
    #endif
    cin >> st;
    p[0] = 1;
    for (int i = 1; i < sz(st); i++) {
        p[i] = p[i - 1] * 37LL % INF;
    }
    for (int i = 0; i < sz(st); i++) {
        if (i) {
            h[i] = h[i - 1];
        }
        h[i] = (h[i] + (st[i] - 'a' + 1) * 1LL * p[i]) % INF;
    }
    for (int i = sz(st) - 1; i >= 0; i--) {
        h1[i] = (h1[i + 1] + (st[i] - 'a' + 1) * 1ll * p[sz(st) - 1 - i]) % INF;
    }
    solve_odd();
    solve_even();
    cout << ans;
    return 0;
}

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