Submission #146562

#	Time	Username	Problem	Language	Result	Execution time	Memory
146562		miguel	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	168 ms	26312 KiB

palindromic

/*
░░░░░░░░░░░░░░░░▄▄█▀▀██▄▄░░░░░░░
░░░░░░░░░░░░░▄█▀▀░░░░░░░▀█░░░░░░
░░░░░░░░░░░▄▀░░░░░░░░░░░░░█░░░░░
░░░░░░░░░▄█░░░░░░░░░░░░░░░█░░░░░
░░░░░░░██▀░░░░░░░▄▄▄░░▄░█▄█▄░░░░
░░░░░▄▀░░░░░░░░░░████░█▄██░▀▄░░░
░░░░█▀░░░░░░░░▄▄██▀░░█████░██░░░
░░░█▀░░░░░░░░░▀█░▀█▀█▀▀▄██▄█▀░░░
░░░██░░░░░░░░░░█░░█░█░░▀▀▄█▀░░░░
░░░░█░░░░░█░░░▀█░░░░▄░░░░░▄█░░░░
░░░░▀█░░░░███▄░█░░░░░░▄▄▄▄█▀█▄░░
░░░░░▀██░░█▄▀▀██░░░░░░░░▄▄█░░▀▄░
░░░░░░▀▀█▄░▀▄▄░▄░░░░░░░███▀░░▄██
░░░░░░░░░▀▀▀███▀█▄░░░░░█▀░▀░░░▀█
░░░░░░░░░░░░▄▀░░░▀█▄░░░░░▄▄░░▄█▀
░░░▄▄▄▀▀▀▀▀█▀░░░░░█▄▀▄▄▄▄▄▄█▀▀░░
░▄█░░░▄██▀░░░░░░░░░█▄░░░░░░░░░░░
█▀▀░▄█░░░░░░░░░░░░░░▀▀█▄░░░░░░░░
█░░░█░░░░░░░░░░░░░░░░░░█▄░░░░░░░
*/
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define x first
#define y second
#define pi pair <int, int>
#define vi vector <int>
#define L nod<<1
#define R ((nod<<1)|1)
#define mp make_pair
const ll mod = 1000000007;
const ll nmax=1000003;
#define int ll
string s;
int p=27, pw[1000010], n, q, h[1000010];

int g(int l, int r){
    return ((h[r]-h[l-1]*pw[r-l+1])%mod+mod)%mod;
}

int solve(int st, int l, int r, int fin){
    if(l>r) return 0;
    else if(st==l && l==r && r==fin) return 1;
    int s1=g(st, l), s2=g(r, fin);
    if(s1==s2){
        return 2+solve(l+1, l+1, r-1, r-1);
    }
    else{
        if(r-l<=2) return 1;
        return solve(st, l+1, r-1, fin);
    }
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    pw[0]=1;
    for(int i=1; i<=1000001; i++) pw[i]=pw[i-1]*p, pw[i]%=mod;
    cin>>q;
    while(q--){
        cin>>s;
        n=s.size();
        for(int i=1; i<=n; i++) h[i]=(h[i-1]*p+s[i-1])%mod;
        cout<<solve(1, 1, n, n)<<"\n";
    }
}

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