Submission #541675

#	Time	Username	Problem	Language	Result	Execution time	Memory
541675		Aldas25	Palindromes (APIO14_palindrome)	C++14	15 / 100	1090 ms	43716 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 300100;
//const ll MOD1 = 1e9+7;
//const ll MOD2 = rng() % ((ll)1e7) + ((ll)1e8);

ll pwr (ll a, ll p, ll m) {
    if (p == 0) return 1ll;
    if (p == 1) return a%m;
    ll ret = pwr(a, p/2, m);
    ret = (ret*ret) % m;
    if (p % 2 == 1) ret *= a%m;
    return ret%m;
}
ll modInv (ll a, ll m) {
    return pwr(a%m, m-2, m);
}

struct stringHash {
    ll pw[MAXN];
    ll pwInv[MAXN];
    ll MOD;
    ll pref[MAXN];
    ll suf[MAXN];
    int n;

    void build (ll _MOD, string s, int _n) {
        MOD = _MOD;
        n = _n;

        pw[0] = 1;
        FOR(i, 1, n+1) pw[i] = (pw[i-1] * 26) % MOD;
        FOR(i, 0, n+1) pwInv[i] = modInv(pw[i], MOD);

        pref[0] = 0;
        FOR(i, 1, n) {
            pref[i] = (pref[i-1] * 26) % MOD;
            pref[i] = (pref[i] + (s[i-1]-'a')) % MOD;
        }

        suf[n+1] = 0;
        for (int i = n; i > 0; i--) {
            suf[i] = (suf[i+1] * 26) % MOD;
            suf[i] = (suf[i] + (s[i-1]-'a')) % MOD;
        }
    }

    ll prefHsh (int i, int j) {
        ll ret = pref[j] - ((pw[j-i+1] * pref[i-1])%MOD) + MOD;
        ret %= MOD;
        //ret = (ret * pwInv[j-1]) % MOD;
        //ret = (ret * pw[n-i]) % MOD;
        return ret;
    }

    ll sufHsh (int i, int j) {
        ll ret = suf[i] - ((pw[j-i+1] * suf[j+1])%MOD) + MOD;
        ret %= MOD;
        //cout << "  suf m = " << MOD << " i = " << i << " j = " << j << "  676 / 26*26 = " << ((676) * pwInv[2])%MOD << endl;
        //cout << "     suf[i] = " << suf[i] << "   ret = " << ret << endl;
        //ret = (ret * pwInv[n-i]) % MOD;
        //ret = (ret * pw[j-1]) % MOD;
        return ret;
    }

    bool pal (int i, int j) {
        return prefHsh(i, j) == sufHsh(i, j);
    }
};

int n;
string s;
stringHash h1, h2;
//map<pair<ll,pair<ll, ll>>, ll> cnt;
unordered_map<ll, ll> toLen;
unordered_map<ll, ll> cnt;

int main()
{
    FAST_IO;

    ll m1 = 1e9+7;
    ll m2 = rng() % ((ll)1e7) + ((ll)1e8);

    cin >> s;
    n = s.length();

    h1.build (m1, s, n);
    h2.build (m2, s, n);

    FOR(i, 1, n) FOR(j, i, n) {
        //cout << " i = " << i << " j = " << j << " pal1 = " << h1.pal(i, j) << " pal2 = " << h2.pal(i, j) << endl;
        //cout << "   pref1 = " << h1.prefHsh(i, j) << " suf1 = " << h1.sufHsh(i, j) << endl;

        if (h1.pal(i, j) && h2.pal(i, j)) {
            //cnt[{j-i+1, {h1.prefHsh(i, j), h2.prefHsh(i, j)}}]++;
            ll h = h1.prefHsh(i, j);
            cnt[h]++;
            toLen[h] = j-i+1;
        }
    }

    ll ans = 0;
    for (auto p : cnt) {
        ll len = toLen[p.f];
        ll c = p.s;
        ans = max(ans, len*c);
    }

    cout << ans << "\n";

    return 0;
}

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