Submission #23275

#	Time	Username	Problem	Language	Result	Execution time	Memory
23275		Nurlykhan	Palindromes (APIO14_palindrome)	C++11	100 / 100	983 ms	35860 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) 5e5 + 10;
const int M = (int) 2e6 + 10;
const ll LINF = (ll) 1e18;
const int mod1 = (int) 1e9 + 7;
const int mod2 = (int) 1e7 + 7;
const double EPS = (double) 1e-9;
string st;
ll ans;
int n;
pii h[N], h1[N];
pii p[N];

int ncol[N], col[N], suff[N], head[N], nsuff[N], pos[N];

bool cmp1(int x, int y) {
   return st[x] < st[y];
}

void suffix_array() {
   for(int i = 0; i < n; i++) suff[i] = i;
   sort(suff, suff + n, cmp1);
   int cn = 0;
   for(int i = 0; i < n; i++) {
      if(!i || st[suff[i]] != st[suff[i - 1]]) {
         col[suff[i]] = cn++;
         head[cn - 1] = i;
      }
      else col[suff[i]] = cn - 1;
   }
   for(int i = 1; i < n; i += i) {
      for(int j = 0; j < n; j++) {
         int k = suff[j] - i;
         if(k < 0) k += n;
         nsuff[head[col[k]]++] = k;
      }
      cn = 0;
      for(int j = 0; j < n; j++)
         suff[j] = nsuff[j];
      for(int j = 0; j < n; j++) {
         if(!j || col[suff[j]] != col[suff[j - 1]] || col[(suff[j] + i) % n] != col[(suff[j - 1] + i) % n])
            ncol[suff[j]] = cn++, head[cn - 1] = j;
         else ncol[suff[j]] = cn - 1;
      }
      for(int j = 0; j < n; j++) col[j] = ncol[j];
   }
   for(int j = 0; j < n; j++) {
      pos[suff[j]] = j;
   }
}

inline pii get_hash(const int &l, const int &r) {
    pii ans = {(h[r].f - (l ? h[l - 1].f : 0) + mod1), (h[r].s - (l ? h[l - 1].s : 0) + mod2)};
    if (ans.f >= mod1) ans.f -= mod1;
    if (ans.s >= mod2) ans.s -= mod2;
    ans.f = ans.f * 1ll * p[sz(st) - 1 - r].f % mod1;
    ans.s = ans.s * 1ll * p[sz(st) - 1 - r].s % mod2;
    return ans;
}

inline pii get_revhash(const int &l, const int &r) {
    pii ans = {(h1[l].f - h1[r + 1].f + mod1), (h1[l].s - h1[r + 1].s + mod2)};
    if (ans.f >= mod1) ans.f -= mod1;
    if (ans.s >= mod2) ans.s -= mod2;
    ans.f = ans.f * 1ll * p[l].f % mod1;
    ans.s = ans.s * 1ll * p[l].s % mod2;
    return ans;
}

inline int first_diff(const pii &x, const 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 m = min(x.s - x.f, y.s - y.f);
    if (get_hash(x.f, x.f + m) == get_hash(y.f, y.f + m)) 
        return x.s - x.f < y.s - y.f;
    return pos[x.f] < pos[y.f];
}

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 = tmp2[i] - tmp1[i] + 2;
        ans = max(ans, occurs * 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 = tmp2[i] - tmp1[i] + 2;
        ans = max(ans, occurs * 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;
    st = st + "#";
    n = sz(st);
    assert(n < N);
    p[0] = {1, 1};
    for (int i = 1; i < n; i++) {
        p[i].f = p[i - 1].f * 37LL % mod1;
        p[i].s = p[i - 1].s * 37LL % mod2;
    }
    for (int i = 0; i < n; i++) {
        if (i) {
            h[i] = h[i - 1];
        }
        h[i].f = (h[i].f + (st[i] + 1) * 1LL * p[i].f) % mod1;
        h[i].s = (h[i].s + (st[i] + 1) * 1LL * p[i].s) % mod2;
    }
    for (int i = n - 1; i >= 0; i--) {
        h1[i].f = (h1[i + 1].f + (st[i] + 1) * 1ll * p[n - 1 - i].f) % mod1;
        h1[i].s = (h1[i + 1].s + (st[i] + 1) * 1ll * p[n - 1 - i].s) % mod2;
    }
    suffix_array();
    solve_odd();
    solve_even();
    cout << ans;
    return 0;
}

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