Submission #1279132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279132		afaf_rafat77	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	194 ms	42524 KiB

palindromic

#include <bits/stdc++.h>
#include <cstring>
#include <cmath>
#define Afaf ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define ull unsigned long long
#define dd double
#define ld long double
#define PQ priority_queue
#define pii pair<int,int>
#define OO LONG_LONG_MAX
#define pll pair<ll,ll>
#define EPS 1e-9
#define PI acos(-1.0)
#define all(x) x.begin(), (x).end()
#define allr(x) x.rbegin(), (x).rend()
#define endd "\n"
#define yes cout << "YES\n"
#define no cout << "NO\n"
using namespace std;
const int base=127,base2=131,mod=1e9+7,mod2=1e9+11, N=1e6+5,M=4e3+10,oo=0x3f3f3f3f,MOD=998244353;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1};
int base_pow[N],base_pow2[N];
vector<pll> pre(N, {0, 0}),pre2(N, {0, 0});
 ll add(ll a, ll b, ll m){ a += b; if (a >= m) a -= m; return a; }
 ll sub(ll a, ll b, ll m){ a -= b; if (a < 0) a += m; return a; }
 ll mul(ll a, ll b, ll m){ return (a * b) % m; }

int pushBack(int h, int base, int mod, int ch) {
    return add(mul(h, base, mod), ch, mod);
}

int popFront(int h, int base_pow, int mod, int ch) { // base_pow = base ^ (len - 1)
    return sub(h, mul(ch, base_pow, mod), mod);
}
void init(){
    base_pow[0] =base_pow2[0] = 1;
    for (int i = 1; i < N; ++i) {
        base_pow[i] = mul(base_pow[i - 1], base, mod);
        base_pow2[i] = mul(base_pow2[i - 1], base2, mod2);
    }
}
pll get(int l,int r){
    auto ret=pre[r];
    int sz=r-l+1;
    l--;
    if(l>=0){
        ret.first=sub(ret.first,mul(pre[l].first,base_pow[sz],mod),mod);
        ret.second=sub(ret.second,mul(pre[l].second,base_pow2[sz],mod2),mod2);
    }
    return ret;
}
pll get2(int l,int r){
    auto ret=pre2[r];
    int sz=r-l+1;
    l--;
    if(l>=0){
        ret.first=sub(ret.first,mul(pre2[l].first,base_pow[sz],mod),mod);
        ret.second=sub(ret.second,mul(pre2[l].second,base_pow2[sz],mod2),mod2);
    }
    return ret;
}
int pushFront(int h, int base_pow, int mod, int ch) { // base_pow = base ^ len
    return add(h, mul(ch, base_pow, mod), mod);
}


int n;
int max_palindrome (int c1, int c2){
    int low = 0, high = min(c1+1, n-c2);
    int best = 0;
    while (low <= high) {
        int mid = (low + high) / 2;
        int l = c1 - mid + 1, r = c2 + mid - 1;
         if (get(l, r) == get2(n - 1 - r, n - 1 - l)){
            best = mid;
            low = mid + 1;
        } else high = mid - 1;
    }
    return best;
}


void go() {
    init();
    string s;
    cin >> s;
    n = s.size();
    int ha1 = 0, ha2 = 0, hb1 = 0, hb2 = 0;
    for (int i = 0; i < n; i++) {
        hb1 = pushBack(hb1, base, mod, s[i]);
        hb2 = pushBack(hb2, base2, mod2, s[i]);
        pre[i] = {hb1, hb2};
        ha1 = pushBack(ha1, base, mod, s[n-1-i]);
        ha2 = pushBack(ha2, base2, mod2, s[n-1-i]);
        pre2[i] = {ha1, ha2};

    }
    ll ans=0,idx=0,idx2=n-1;
    for (int i=0;i<n/2;i++) {
        pll x=get(idx,i),y=get(idx2-(i-idx),idx2);
        // cout<<x.first<<" "<<x.second<<endd;
        // cout<<y.first<<" "<<y.second<<endd;
        if (x.first==y.first and x.second==y.second ) {
            ans+=2;
            if (i+1==idx2-(i-idx))return void(cout<<ans<<endd);
            idx2-=(i+1-idx),idx=i+1;
        }
    }
    cout << ans +1<< endl;

}



int main() {
    Afaf
    //freopen("fortune.in","r",stdin);
    //freopen("output.txt","w",stdout);
    int tc = 1;
    cin >> tc;
    while(tc--){
        go();
    }
}

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