Submission #403752

#	Time	Username	Problem	Language	Result	Execution time	Memory
403752		opukittpceno_hhr	Palindromes (APIO14_palindrome)	C++17	15 / 100	1088 ms	3624 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;

const int INF = 1e9 + 239;

namespace Hash {
    int n;
    string s;

    int req(int i, int j, int len) {
        while (len) {
            if (i < 0 || j >= n) return 0;
            if (s[i] != s[j]) return 0;
            i--;
            j++;
            len--;
        }
        return 1;
    }

    void init(string s_) {
        s = s_;
        n = (int)s.size();
    }
}

namespace SuffixArray {
    int n;
    string s;

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


    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();
        for (int i = 0; i < n; i++) {
            sa.push_back(i);
        }
        sort(sa.begin(), sa.end(), [&](int i, int j) {
            return cmp(i, j) == -1;
        });
        wr.resize(n);
        for (int i = 0; i < n; i++) {
            wr[sa[i]] = i;
        }
    }
}

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);
    int ans = 0;

    //even
    {
        vector<pair<int, int>> ip;
        for (int i = 0; i < n; i++) {
            int mx = -1;
            //TODO
            for (int j = 0; j <= i && i + j <= n; j++) {
                if (Hash::req(i - 1, i, j)) {
                    mx = j;
                }
            }
            ans = max(ans, 2 * mx);
            if (mx != -1) {
                ip.push_back({i, mx});
            }
        }
        sort(ip.begin(), ip.end(), [&](pair<int, int> X, pair<int, int> Y) {
            return SuffixArray::wr[X.first] < SuffixArray::wr[Y.first];
        });
        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)}));
        }
        int sz = (int)val.size();
        for (int i = 0; i < sz; i++) {
            int mn = INF;
            for (int j = i; j < sz; j++) {
                mn = min(mn, val[j]);
                ans = max(ans, (j - i + 2) * (2 * mn));
            }
        }
    }
    //odd
    {
        vector<pair<int, int>> ip;
        for (int i = 0; i < n; i++) {
            int mx = -1;
            //TODO
            for (int j = 0; j <= i && i + j + 1 <= n; j++) {
                if (Hash::req(i - 1, i + 1, j)) {
                    mx = j;
                }
            }
            ans = max(ans, 2 * mx + 1);
            if (mx != -1) {
                ip.push_back({i, mx});
            }
        }
        sort(ip.begin(), ip.end(), [&](pair<int, int> X, pair<int, int> Y) {
            return SuffixArray::wr[X.first] < SuffixArray::wr[Y.first];
        });
        vector<int> val;
        for (int i = 0; i + 1 < (int)ip.size(); i++) {
            val.push_back(min({ip[i].second + 1,  ip[i + 1].second + 1, SuffixArray::lcp(ip[i].first, ip[i + 1].first)}));
        }
        int sz = (int)val.size();
        for (int i = 0; i < sz; i++) {
            int mn = INF;
            for (int j = i; j < sz; j++) {
                mn = min(mn, val[j]);
                ans = max(ans, (j - i + 2) * (2 * mn - 1));
            }
        }
    }

    cout << ans << endl;
}

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