Submission #916332

#	Time	Username	Problem	Language	Result	Execution time	Memory
916332		vjudge1	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	5072 ms	52288 KiB

palindromic

#include <bits/stdc++.h>
#define MAX 1000001
#define pb push_back
#define ins insert 
using namespace std; 
typedef long long ll; 
int n,q,t=1,m,n2,m2,k,x,y,z,x2,y2,z2,a[MAX],b[MAX],d[MAX],e[MAX],dp[1][2],tim,res;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string s[MAX],str[1];
//ll e[2001][2001];
//ll e1[1001][1001]; 
string s1,s2,s3;
const int mod = 998244353;
int N=201326611,M=402653189,K=26,N1,M1;
int powmod(int x,int y,int md){
    if(y==0){
        return 1;
    }
    x%=md;
    if(x==0){
        return 0;
    }
    int res=1;
    while(y>0){
        if(y%2){
            res=(1ll*res*x)%md;
        }
        y/=2;
        x=(1ll*x*x)%md;
    }
    return res;
}
int inv(int n,int md){
    return powmod(n,md-2,md);
}
int gh1(int l,int r){
    int h=(a[r]-a[l-1]+N)%N;
    h=(1ll*h*e[l-1])%N;
    return h; 
}
int gh2(int l,int r){
    int h=(b[r]-b[l-1]+M)%M;
    h=(1ll*h*d[l-1])%M;
    return h;
}
void solve(){
    cin >> s1;
    n=(int)s1.size(); 
    for(int i=0;i<n;i++){
        e[i]=inv(powmod(K,i,N),N); 
    }
    int h,h1,h2,h3; 
    h=h1=0; 
    h2=h3=1; 
    for(int i=0;i<n;i++){
        a[i+1]=((ll)a[i]+(1ll*(s1[i]-'a'+1)*h2)%N)%N;
        h2=(1ll*h2*K)%N; 
    }
    int l,r; 
    l=1; 
    r=n; 
    ll res=0; 
    while(r>=l){
        ll x=1; 
        while(l+x-1<r-x+1){
            if(gh1(l,l+x-1)==gh1(r-x+1,r)){
                break;
            }
            x++;
        }
        if(l+x-1<r-x+1){
            res+=2; 
            l+=x;
            r-=x; 
        }
        else{
            res++;
            break; 
        }
    }
    cout << res << "\n"; 
}
signed main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    //USACO("diamond");
    //freopen("meta_game_input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    cin >> t;
    ll cnt1=1;
    while(t--){
        //cout << "Case #" << cnt1 << ": ";
        solve();
        cnt1++;
    }
    return 0;
}
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ifstream fin("template.in");
ofstream fout("template.out");
*/
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ifstream fin("template.in");
ofstream fout("template.out");
*/
/*
ll b[51][51];
b[0][0] = 1;
    for (int n = 1; n <= 50; ++n){
        b[n][0] = b[n][n] = 1;
        for (int k = 1; k < n; ++k)
            b[n][k] = b[n - 1][k - 1] + b[n - 1][k];
    }
*/

Compilation message (stderr)

palindromic.cpp: In function 'void solve()':
palindromic.cpp:52:9: warning: variable 'h' set but not used [-Wunused-but-set-variable]
   52 |     int h,h1,h2,h3;
      |         ^

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