Submission #401344

#	Time	Username	Problem	Language	Result	Execution time	Memory
401344		aymane7	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	956 ms	36068 KiB

palindromic

#include<bits/stdc++.h>
#pragma GCC optimize("O2")
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define all(c) c.begin(), c.end()
#define endl "\n"
#define sz(u) (int)(u.size())
#define L(x)(2*x)
#define R(x)(2*x+1)
#define M(x,y)((x+y)/2)
#define int long long
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int p=131,md=1e9+7;
const int N=1e6;
vector<int> pw(N),pref;
void precalc(){
    pw[0]=1;
    for(int i=1;i<N;i++)
        pw[i]=(pw[i-1]*p)%md;
}
int bpow(int a,int k){
    int ans=1;
    while(k){
        if(k&1)
            ans=(ans*a)%md;
        a=(a*a)%md;
        k>>=1;
    }
    return ans;
}
int inv(int a){
    return bpow(a,md-2);
}
int get_hash(int l,int r){
    if(l==0)
        return pref[r];
    int ans=((pref[r]-pref[l-1])%md +md)%md;
    ans=(ans*inv(pw[l]))%md;
    return ans;
}
void solve(){
    string s;
    cin>>s;
    int n=sz(s);
    pref=vector<int>(n,0);
    for(int i=0;i<n;i++){
        if(i!=0)
            pref[i]=pref[i-1];
        pref[i]=(pref[i]+ (pw[i]*s[i])%md )%md;
    }
    vector<vector<int>> pos(26);
    vector<int> cur(26,0);
    for(int i=0;i<n;i++)
        pos[s[i]-'a'].PB(i);
    int ans=0,curl=0,curr=n-1;
    while(1){
        //cout<<curl<<" "<<curr<<endl;
        int c=s[curr]-'a';
        bool fnd=0;
        for(int j=cur[c];j<sz(pos[c]);j++){
            int i=pos[c][j];
            if(i>=curl && curr+curl>2*i && get_hash(curl,i)==get_hash(curr+curl-i,curr)){
                fnd=1;
                ans+=2;
                curr=curr+curl-i-1;
                curl=i+1;
                cur[c]=j+1;
                break;
            }
        }
        if(fnd){
            if(curl==curr){
                ans++;
                break;
            }
            if(curl>curr)
                break;
        }
        else{
            ans++;
            break;
        }
    }
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    precalc();
    int t;
    cin>>t;
    while(t--){
        solve();
        cout<<endl;
    }
}

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