Submission #1015539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015539		0pt1mus23	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	120 ms	28620 KiB

palindromic

#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ins insert
#define pb push_back
#define int long long int
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()
#define hash FhashF
const int mod = 159766601, sze = 2e6+10, inf = INT_MAX, P = 1453;

int prime[sze];
int hash[sze];

int qry(int l,int r,int lx,int rx){
    int a = (prime[l] * 1LL * (hash[rx+1] - hash[lx])%mod + mod) %mod;
    int b = (prime[lx] * 1LL * (hash[r+1] - hash[l])%mod + mod)%mod;
    // cout<<a<<" "<<b<<endl;
    return (a==b);
}

void mal(){
    string s;
    cin>>s;
    int n= s.size();
    prime[0]=1;
    for(int i=1;i<=n;i++){
        prime[i]=(prime[i-1]*P)%mod;
    }
    for(int i =0;i<n;i++){
        hash[i+1]=(hash[i] + (((s[i]-'a'+1) * prime[i]) %mod) + mod )%mod;
    }
    int ans=0;
    int l =0;
    int r = n-1;
    for(int i =0;i<n;i++){
        // cout<<i<<" -> "<<l<<":"<<r<<endl;
        if(l>=r){
            break;
        }
        int len = i-l +1;
        int l1 = l;
        int r1=i;
        int l2 = r-len +1;
        int r2=r;
        
        if(r1>=l2){
            break;
        }
        int f = qry(l1,r1,l2,r2);
        // cout<<l1<<":"<<r1<<" , "<<l2<<":"<<r2<<" = "<<f<<endl;
        
        if(f){
            ans+=2;
            l=i+1;
            r = l2 -1;
        }
    }
    if(l<=r){
        ans++;
    }
    drop(ans);
}
 
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    clock_t z = clock();
    int tt = 1;
    cin>>tt;
    
    while(tt--){
        mal();        
    }
} 
 

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:69:13: warning: unused variable 'z' [-Wunused-variable]
   69 |     clock_t z = clock();
      |             ^

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