Submission #1073847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073847		vjudge1	Palindromes (APIO14_palindrome)	C++17	47 / 100	1074 ms	36176 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
void print() {cout<<endl;}
template<typename T,typename... E>
void print(T t,E... e) {cout<<t<<(sizeof...(e)?" ":"");print(e...);}
#define forn(i,x,n) for(int i=int(x);i<int(n);++i)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define F first
#define S second
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;

inline int add(int a, int b, const int &mod) { return a+b >= mod ? a+b-mod : a+b; }
inline int sbt(int a, int b, const int &mod) { return a-b < 0 ? a-b+mod : a-b; }
inline int mul(int a, int b, const int &mod) { return 1ll*a*b % mod; }

const int X[] = {257, 359};
const int MOD[] = {(int)1e9+7, (int)1e9+9};
vector<int> xpow[2];

struct hashing {
    vector<int> h[2];

    hashing(string &s) {
        int n = s.size();
        for (int j = 0; j < 2; ++j) {
            h[j].resize(n+1);
            for (int i = 1; i <= n; ++i) {
                h[j][i] = add(mul(h[j][i-1], X[j], MOD[j]), s[i-1], MOD[j]);
            }
        }
    }
    // Hash del substring en el rango [i, j)
    ll value(int l, int r) {
        int a = sbt(h[0][r], mul(h[0][l], xpow[0][r-l], MOD[0]), MOD[0]);
        int b = sbt(h[1][r], mul(h[1][l], xpow[1][r-l], MOD[1]), MOD[1]);
        return (ll(a)<<32) + b;
    }
};

void calc_xpow(int mxlen) {
    for (int j = 0; j < 2; ++j) {
        xpow[j].resize(mxlen+1, 1);
        for (int i = 1; i <= mxlen; ++i) {
            xpow[j][i] = mul(xpow[j][i-1], X[j], MOD[j]);
        }
    }
}

string parse(string &s) {
    string t = "%";
    for (auto &c : s) t.pb('#'), t.pb(c);
    t += "#$";
    return t;
}

vector<int> manacher(string &s) {
    string t = parse(s);
    int n = t.size();
    vector<int> p(n, 0);
    int c = 0, r = 0;
    for (int i = 1; i < n-1; i++) {
        int j = c - (i-c) ;
        if (r > i) p[i] = min(r-i, p[j]);
        while (t[i+1+p[i]] == t[i-1-p[i]]) 
            p[i]++;
        if (i+p[i] > r) {
            c = i;
            r = i+p[i];
        }
    }
    return p;
}

const int N = 3e5+5;
set<ll> palin[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    string s;
    cin >> s;
    int n = s.size();
    auto p = manacher(s);
    int m = p.size();
    
    calc_xpow(n);
    hashing hs(s);
    set<int> sizes;
    forn(i, 0, m) {
        if (!p[i]) continue;
        int l = (i - 1 - p[i]) / 2;
        int r = l + p[i];
        sizes.insert(r-l);
        ll value = hs.value(l, r);
        palin[r-l].insert(value);
    }
    
    ll ans = 0;
    for (auto &sz : sizes) {
        int mx = 0;
        map<ll, int> cnt;
        forn(i, 0, n-sz+1) {
            ll value = hs.value(i, i+sz);
            if (palin[sz].count(value)) {
                mx = max(mx, ++cnt[value]);
            }
        }
        ans = max(ans, 1ll * mx * sz);
    }
    print(ans);
}

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