Submission #403788

#	Time	Username	Problem	Language	Result	Execution time	Memory
403788		opukittpceno_hhr	Palindromes (APIO14_palindrome)	C++17	23 / 100	1100 ms	56388 KiB

palindrome

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

typedef long long ll;

const int ALP = 26;

namespace Hash {
    const int MOD = 1e9 + 7;
    const int BASE = 31;

    int add(int a, int b) {
        if (a + b < MOD) {
            return a + b;
        }
        return a + b - MOD;
    }

    int sub(int a, int b) {
        if (a >= b) {
            return a - b;
        }
        return a - b + MOD;
    }

    int mul(int a, int b) {
        return 1LL * a * b % MOD;
    }

    int n;
    string s;

    vector<int> pw;
    vector<int> h;
    vector<int> rh;

    int req(int i, int j, int len) {
        i = n - 1 - i;
        int F = sub(rh[i + len], mul(rh[i], pw[len]));
        int S = sub(h[j + len], mul(h[j], pw[len]));
        return F == S;
    }

    void init(string s_) {
        s = s_;
        n = (int)s.size();
        pw.resize(n + 1);
        h.resize(n + 1);
        rh.resize(n + 1);
        pw[0] = 1;
        for (int i = 0; i < n; i++) {
            pw[i + 1] = mul(pw[i], BASE);
        }
        for (int i = 0; i < n; i++) {
            h[i + 1] = add(s[i], mul(h[i], BASE));
        }
        reverse(s.begin(), s.end());
        for (int i = 0; i < n; i++) {
            rh[i + 1] = add(s[i], mul(rh[i], BASE));
        }
        reverse(s.begin(), s.end());
    }
}

namespace SuffixArray {
    int n;
    string s;

    vector<int> sa;
    vector<int> wr;

    vector<tuple<int, int, int>> tos;

    void do_sort() {
        sort(tos.begin(), tos.end());
    }

    void build_sa() {
        s.push_back(0);
        n++;

        vector<int> cur_class(n);
        {
            vector<char> hv;
            for (auto c : s) {
                hv.push_back(c);
            }
            sort(hv.begin(), hv.end());
            hv.resize(unique(hv.begin(), hv.end()) - hv.begin());
            for (int i = 0; i < n; i++) {
                cur_class[i] = lower_bound(hv.begin(), hv.end(), s[i]) - hv.begin();
            }
        }
        for (int l = 1; l < n; l *= 2) {
            for (int i = 0; i < n; i++) {
                tos.push_back({cur_class[i], cur_class[(i + l) % n], i});
            }
            do_sort();
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                cur_class[get<2>(tos[i])] = cnt;
                if (i > 0) {
                    cnt += (get<0>(tos[i]) != get<0>(tos[i - 1]) || get<1>(tos[i]) != get<1>(tos[i - 1]));
                }
            }
        }
        sa.resize(n);
        for (int i = 0; i < n; i++) {
            sa[i] = cur_class[i];
        }
        wr.resize(n);
        sa.erase(sa.begin());
        n--;
        for (int i = 0; i < n; i++) {
            wr[sa[i]] = i;
        }
    }


    int lcp(int i, int j) {
        //TODO
        int ans = 0;
        while (i < n && j < n) {
            if (s[i] != s[j]) {
                return ans;
            }
            ans++;
            i++;
            j++;
        }
        return ans;
    }

    int eq(int i, int j, int len) {
        return lcp(i, j) >= len;
    }

    int cmp(int i, int j) {
        int sk = lcp(i, j);
        i += sk;
        j += sk;
        if (i == n && j == n) {
            return 0;
        }
        if (i == n || s[i] < s[j]) {
            return -1;
        } else {
            return 1;
        }
    }

    void init(string s_) {
        s = s_;
        n = (int)s.size();
        build_sa();
        wr.resize(n);
        for (int i = 0; i < n; i++) {
            wr[sa[i]] = i;
        }
    }
}

void solve(vector<int> v, int ml, int add, ll &ans) {
    int n = (int)v.size();
    vector<int> l(n);
    vector<int> r(n);
    {
        vector<int> st;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && v[st.back()] >= v[i]) {
                st.pop_back();
            }
            if (st.empty()) {
                l[i] = -1;
            } else {
                l[i] = st.back();
            }
            st.push_back(i);
        }
    }
    {
        vector<int> st;
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && v[st.back()] >= v[i]) {
                st.pop_back();
            }
            if (st.empty()) {
                r[i] = n;
            } else {
                r[i] = st.back();
            }
            st.push_back(i);
        }
    }
    for (int i = 0; i < n; i++) {
        ans = max(ans, (ll)(r[i] - l[i]) * (v[i] * ml + add));
    }
}

int cnt[ALP];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cin >> s;
    int n = (int)s.size();

    Hash::init(s);
    SuffixArray::init(s);
    ll ans = 0;

    auto cmp = [&](pair<int, int> X, pair<int, int> Y) {
        int i1, len1, i2, len2;
        tie(i1, len1) = X;
        tie(i2, len2) = Y;
        int sk = SuffixArray::lcp(i1, i2);
        if (sk >= len1 || sk >= len2) {
            return len1 < len2;
        }
        i1 += sk;
        i2 += sk;
        return (i1 == n || s[i1] < s[i2]);
    };

    //single
    {
        for (int i = 0; i < n; i++) {
            cnt[s[i] - 'a']++;
            ans = max(ans, (ll)cnt[s[i] - 'a']);
        }
    }

    //even
    {
        vector<pair<int, int>> ip;
        for (int i = 0; i < n; i++) {
            int mx = -1;
            int l = -1;
            int r = n +1;
            while (r  - l > 1) {
                int mid = (r + l) / 2;
                if (mid <= i && mid + i <= n && Hash::req(i - 1, i, mid)) {
                    l = mid;
                } else {
                    r = mid;
                }
            }
            mx = l;
            ans = max(ans, (ll)2 * mx);
            if (mx != -1) {
                ip.push_back({i, mx});
            }
        }
        sort(ip.begin(), ip.end(), cmp);
        vector<int> val;
        for (int i = 0; i + 1 < (int)ip.size(); i++) {
            val.push_back(min({ip[i].second, ip[i + 1].second, SuffixArray::lcp(ip[i].first, ip[i + 1].first)}));
        }
        solve(val, 2, 0, ans);
    }
    //odd
    {
        vector<pair<int, int>> ip;
        for (int i = 0; i < n; i++) {
            int mx = -1;
            int l = -1;
            int r = n +1;
            while (r  - l > 1) {
                int mid = (r + l) / 2;
                if (mid <= i && mid + i + 1 <= n && Hash::req(i - 1, i + 1, mid)) {
                    l = mid;
                } else {
                    r = mid;
                }
            }
            mx = l;
            ans = max(ans, (ll)2 * mx + 1);
            if (mx != -1) {
                ip.push_back({i, mx + 1});
            }
        }
        sort(ip.begin(), ip.end(), cmp);
        vector<int> val;
        for (int i = 0; i + 1 < (int)ip.size(); i++) {
            val.push_back(min({ip[i].second,  ip[i + 1].second, SuffixArray::lcp(ip[i].first, ip[i + 1].first)}));
        }
        solve(val, 2, -1, ans);
    }
    cout << ans << endl;
}

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