Submission #541726

#	Time	Username	Problem	Language	Result	Execution time	Memory
541726		Aldas25	Palindromes (APIO14_palindrome)	C++14	15 / 100	1042 ms	78188 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, ll>, ll> cnt;
vector<pair<int, pair<ll,ll>>> srt;
map<pair<ll, ll>, pair<ll, ll>> shorten;
set<pair<ll, ll>> done;

void proc (int fr, int to) {

    ll hsh1 = h1.prefHsh(fr, to);
    ll hsh2 = h2.prefHsh(fr, to);
    cnt[{hsh1, hsh2}]++;

    while (true){
        hsh1 = h1.prefHsh(fr, to);
        hsh2 = h2.prefHsh(fr, to);
        if (done.count({hsh1, hsh2})) return;

        //cout << " fr = " << fr << " to = " << to << " hsh1 = " << hsh1 << " hsh2 = " << hsh2 << endl;

        done.insert({hsh1, hsh2});
        //toLen({hsh1, hsh2}) = to-fr+1;
        srt.pb({to-fr+1, {hsh1, hsh2}});

        fr += 1;
        to -= 1;
        if (fr > to) return;

        ll h11 = h1.prefHsh(fr, to);
        ll h22 = h2.prefHsh(fr, to);

        shorten[{hsh1, hsh2}] = {h11, h22};

        //cout << "    shorten to h11 = " << h11 << " h22 = " << h22 << endl;
    }
}

int main()
{
    FAST_IO;

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

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

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

    FOR(i, 1, 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;

        /// b=0 - odd len pal, b=1 - even len pal

        FOR(b, 0, 1) {
            int le = 0, ri = n;
            if (i + b > n) continue;
            while (le < ri) {
                int m = (le+ri+1)/2;
                int fr = i-m, to = i+m+b;
                if (fr < 1 || to > n)
                    ri = m - 1;
                else if (h1.pal(fr, to) && h2.pal(fr, to))
                    le = m;
                else ri = m-1;
            }

            if (i-le > 0 && i+le+b <= n && h1.pal(i-le, i+le+b) && h2.pal(i-le, i+le+b))
                proc (i-le, i+le+b);
        }
    }

    ll ans = 0;

    sort(srt.begin(), srt.end());
    reverse(srt.begin(), srt.end());

    for (auto p : srt) {
        ll len = p.f;
        ll hsh1 = p.s.f, hsh2 = p.s.s;
        ll c = cnt[{hsh1, hsh2}];
        //cout << "  len = " << len << " c  = " << c << " hsh1 = " << hsh1 << " hsh2 = " << hsh2 << endl;
        ans = max(ans, len  * c);
        if (shorten.find({hsh1, hsh2}) != shorten.end()) {
            cnt[shorten[{hsh1, hsh2}]] += c;
          //  cout << "     sh to: " << shorten[{hsh1, hsh2}].f << "  " << shorten[{hsh1, hsh2}].s << endl;
        }
    }

    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