Submission #1310998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310998		tarner_exe	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	272 ms	25576 KiB

palindromic

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define elif else if
#define ft first
#define sc second
#define pII pair<int,int>
#define pb push_back

const int sizen = 2e6+11;
const int p = 31;
const int modd = 1e9+321;

int pt[sizen];
int hsh[sizen];

int t,N;

string st;

void pre_pr()
{
    pt[0]=1;
    for (int i = 1 ;i <= sizen-3; i++)
    {
        pt[i] = (pt[i-1]*p)%modd;
    }
}
void hshs()
{
    for (int i = 1 ; i <= st.size() ; i++)
    {
        hsh[i] = ((hsh[i-1]*p)%modd + ((st[i-1]-'a')+1))%modd;
    }
}

bool zgodnosc(int l_p , int l_k , int p_p , int p_k)
{
    if(l_k == 2)
    {
        //cout << l_p << ' ' << l_k << " " << p_p << " " << p_k << '\n';
        //cout << hsh[l_k] << " - " << hsh[l_p-1] << " * " << pt[l_k-l_p+1] << "\n";
        //cout << hsh[p_k] << " - " << hsh[p_p-1] << " * " << pt[p_k-p_p+1] << "\n"; 
    }
    int LEWY = (hsh[l_k] - ((hsh[l_p-1]*pt[l_k-l_p+1])%modd) + modd)%modd;
    int PRAWY =(hsh[p_k] - ((hsh[p_p-1]*pt[p_k-p_p+1])%modd) + modd)%modd;
    if(LEWY == PRAWY)
    {
        return true;
    }
    return false;
}

void solve()
{
    cin >> st;
    N = st.size();
    hshs();
    int last_l=1;
    
    int last_p = N;
    
    int w = 0;
    
    for (int i = 1 ; i <= st.size() ; i++)
    {
        if(zgodnosc(last_l, i, last_p-(i-last_l) , last_p))
        {
            //cout << i << '\n';
            if(i == last_p)
            {
                w ++;
                cout << w << '\n';
                return; 
            }
            elif(i < last_p)
            {
                w += 2;
            }
            last_p = last_p-(i-last_l+1);
            last_l = i+1;
        }
    }
    cout << w << "\n";
}
signed main()
{
    pre_pr();
    cin >> t;
    while(t--)
    {
        solve();
    }
}

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