Submission #850869

#	Time	Username	Problem	Language	Result	Execution time	Memory
850869		dungz	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	92 ms	20748 KiB

palindromic

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
ll const MOD=1e9+9,base=31;
ll p[1000005];
void sol()
{
    string s;
    cin>>s;
    s=" "+s;
    int i=1,j=s.size()-1;
    ll hash1=0,hash2=0;
    int d=0,ans=0;
    p[0]=1;
    for(int i=1;i<=s.size()-1;i++)
    {
        p[i]=(p[i-1]*base)%MOD;
    }
    int flag=1;
    for(int step=1;step<=s.size()/2-(s.size()%2==0?1:0);step++)
    {
        hash1=(hash1*base+s[i]-'a'+1)%MOD;
        hash2=(hash2+(s[j]-'a'+1)*p[d])%MOD;
        flag=1;
        if(hash1==hash2)
        {
            flag=0;
            hash1=0;
            hash2=0;
            ans+=2;
            d=-1;
        }
        d++;
        i++,j--;
    }
    if(s.size()%2==1) cout<<ans+flag<<endl;
    else cout<<ans+1<<endl;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
   
    int t;
    cin>>t;
    while(t--)
    {
        sol();
    }
}

Compilation message (stderr)

palindromic.cpp: In function 'void sol()':
palindromic.cpp:16:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i=1;i<=s.size()-1;i++)
      |                 ~^~~~~~~~~~~~
palindromic.cpp:21:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int step=1;step<=s.size()/2-(s.size()%2==0?1:0);step++)
      |                    ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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