Submission #1307112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307112		random_user27	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	99 ms	19012 KiB

palindromic

//In The Name Of God
 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;
typedef pair<ll , ll> pll;
 
#define pb push_back
#define endl '\n'
#define lc id*2
#define rc id*2+1
#define mid (l+r)/2
#define test(x) cout<<x,exit(0)
#define fast (ios_base::sync_with_stdio(false), cin.tie(NULL));

const int maxn=1e6+10;
const int mod=1e9+7;
const int base=37;
ll pw[maxn];
ll par[maxn];

ll chk(int l1,int l2,int sz){
    ll val1=par[l2+sz-1]-par[l2-1]+mod;
    val1%=mod;
    val1*=pw[l1];val1%=mod;
    ll val2=par[l1+sz-1]-par[l1-1]+mod;
    val2%=mod;
    val2*=pw[l2];val2%=mod;
    return (val1==val2);
    
}

int main(){
    fast;
    pw[0]=1;
    for(int i=1;i<maxn;i++){
        pw[i]=pw[i-1]*base%mod;
    }
    int t;cin>>t;
    while(t--){
        string x;cin>>x;
        int n=x.size();
        for(int i=1;i<=n;i++){
            par[i]=par[i-1]+(x[i-1]-'a')*pw[i];
            par[i]%=mod;
        }
        int res_l=1;
        int res_r=n;
        int cnt=0;
        while(res_l<=res_r){
            int ans=res_r-res_l+1;
            cnt++;
            for(int sz=1;sz<=res_r-res_l;sz++){
                if(sz*2<=ans and chk(res_l,res_r-sz+1,sz)){
                    cnt++;
                    ans=sz;break;
                }
            }
            res_l+=ans;
            res_r-=ans;
        }
        cout<<cnt<<endl;
    }
}

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