Submission #110796

#	Time	Username	Problem	Language	Result	Execution time	Memory
110796		someone_aa	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	498 ms	29644 KiB

palindromic

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1000010;
const ll mod = 1000000007;
const ll p = 61;
ll pref[N], inv[N];
string code;

void init(string x) {
    x = "a" + x;
    pref[1] = x[1]-'a'+1;
    ll pp = p;
    for(int i=2;i<x.length();i++) {
        pref[i] = 1LL*(pref[i-1]+((x[i]-'a'+1)*pp)%mod)%mod;
        pp *= p; pp%=mod;
    }
}

ll power(ll a, ll b) {
    if(b==0) return 1LL;
    else if(b==1) return 1LL*(a%mod);
    else {
        if(b%2==1) {
            ll temp = power(a, b-1);
            return (a*temp)% mod;
        }
        else {
            ll temp = power(a, b/2);
            return (temp*temp)%mod;
        }
    }
}

ll calc_mod(ll a) {
    return 1LL*(a%mod + mod)%mod;
}

ll get_hash(int li, int ri) {
    ll x = pref[ri+1]-pref[li];
    x = calc_mod(x);
    ll y = inv[li];
    return 1LL*(x*y) % mod;
}

int solve(string x) {
    if(x.length()==1) {
        return 1;
    }

    memset(pref,0,sizeof(pref));
    init(x);
    int n = x.length();
    int l1 = 0, r1=0;
    int l2 = n-1, r2=n-1;

    int br = 0;
    while(true) {
        if(r1+1==l2) {
            br++;
            if(get_hash(l1,r1) == get_hash(l2,r2)) br++;
            break;
        }

        if(r1+1==l2-1) {
            br++;
            if(get_hash(l1,r1) == get_hash(l2,r2)) br+=2;
            break;
        }

        if(get_hash(l1, r1) == get_hash(l2, r2)) {
            br+=2;
            l1 = r1 = r1+1;
            l2 = r2 = l2-1;
        }
        else {
            r1++;
            l2--;
        }
    }
    return br;
}

void init_start() {
    ll pp = 1LL;
    for(int i=0;i<N;i++) {
        inv[i] = power(pp, mod-2);
        pp *= p; pp%=mod;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    init_start();
    int te;
    cin>>te;
    while(te--) {
        cin>>code;
        cout<<solve(code)<<"\n";
    }
    return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'void init(std::__cxx11::string)':
palindromic.cpp:14:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=2;i<x.length();i++) {
                 ~^~~~~~~~~~~

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