Submission #1177257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177257		0xessam	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	117 ms	19000 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define int long long
#define el '\n' ;
#define ff first
#define ss second
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define vii vector<pii>
#define yes cout<<"YES"<<'\n';
#define no cout<<"NO"<<'\n';
#define minit(v, x...) v = min({v, x})
#define maxit(v, x...) v = max({v, x})
#define stop(x) {cout << x << '\n'; continue ;}
const ll N = 2e5 + 5, M = 1e7 + 5, MOD = 1e9 + 7, oo = 1e18;

int B1, B2, MOD1, MOD2;
vector<ll> pw1, pw2;

void init(int sz) {
    mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
    auto rnd = [&](int l, int r) { return uniform_int_distribution<int>(l, r)(mt); };

    auto is_prime = [&] (int x) -> bool {
        for (int i = 2; i * i <= x; ++i) if (x % i == 0) return false;
        return true;
    };
    B1 = rnd(100, 500);
    B2 = rnd(100, 500);
    MOD1 = rnd(2e8, 2e9);
    MOD2 = rnd(2e8, 2e9);

    while (!is_prime(MOD1)) MOD1--;
    while (MOD1 == MOD2 || !is_prime(MOD2)) MOD2--;

    pw1.assign(sz + 1, 1);
    pw2.assign(sz + 1, 1);
    for (int i = 1; i <= sz; i++) {
        pw1[i] = (pw1[i - 1] * B1) % MOD1;
        pw2[i] = (pw2[i - 1] * B2) % MOD2;
    }
}

class Hashing {
private:
    ll h1 = 0, h2 = 0, inv1, inv2;
    deque<char> d;
    int len = 0;

    ll power(ll a, ll b, ll m) {
        ll ans = 1;
        while (b) {
            if (b & 1) ans = (ans * a) % m;
            a = (a * a) % m;
            b >>= 1;
        }
        return ans;
    }

public:
    Hashing() {
        inv1 = power(B1, MOD1 - 2, MOD1);
        inv2 = power(B2, MOD2 - 2, MOD2);
    }

    void push_back(char x) {
        x = x - 'a' + 1;
        h1 = (h1 * B1 + x) % MOD1;
        h2 = (h2 * B2 + x) % MOD2;
        len++;
        d.emplace_back(x);
    }

    void push_front(char x) {
        x = x - 'a' + 1;
        h1 = (h1 + x * pw1[len] % MOD1) % MOD1;
        h2 = (h2 + x * pw2[len] % MOD2) % MOD2;
        len++;
        d.emplace_front(x);
    }

    void pop_back() {
        if (len == 0) return;
        char x = d.back();
        d.pop_back();
        h1 = (h1 - x + MOD1) % MOD1;
        h1 = (h1 * inv1) % MOD1;
        h2 = (h2 - x + MOD2) % MOD2;
        h2 = (h2 * inv2) % MOD2;
        len--;
    }

    void pop_front() {
        if (len == 0) return;
        char x = d.front();
        d.pop_front();
        len--;
        h1 = ((h1 - x * pw1[len] % MOD1) + MOD1) % MOD1;
        h2 = ((h2 - x * pw2[len] % MOD2) + MOD2) % MOD2;
    }

    void clear() {
        h1 = h2 = len = 0;
        d.clear();
    }

    bool operator==(const Hashing &H) const {
        return H.h1 == h1 && H.h2 == h2;
    }

    string GetString() {
        return string(d.begin(), d.end());
    }

    pair<int, int> GetHash() {
        return {h1, h2};
    }
};

int32_t main() {
//#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    init(1e6 + 5) ;
    int T ; cin >> T ; while (T--) {
        string s ; cin >> s ;
        Hashing a , b;
        int l = 0 , r = s.size() - 1 ;
        int ans = 1 ;
        while (l < r) {
            a.push_back(s[l++]) ;
            b.push_front(s[r--]) ;
            if (a.GetHash() == b.GetHash()) {
                ans += 2 ;
                a.clear() ;
                b.clear() ;
            }
        }
        ans -= (l > r && !a.GetHash().ff ) ;
        cout << ans << "\n";
    }


}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40