Submission #393348

#	Time	Username	Problem	Language	Result	Execution time	Memory
393348		rumen_m	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	159 ms	28508 KiB

palindromic

# include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
const long long base = 27;
const long long maxn = 1e6+5;
long long hashes[maxn];
long long poww[maxn];
long long find_hash(long long from, long long to)
{
    long long pref = (hashes[from-1]*poww[to-from+1])%MOD;
    long long ans = (hashes[to]+MOD-pref)%MOD;
    return ans;
}
void solve()
{
    string s;
    cin>>s;
    long long ans = 0;
    poww[0] = 1;
    hashes[0] = 0;
    long long i;
    for(i = 1; i<=s.size();i++)
    {
        long long ch = s[i-1]-'a'+1;
        poww[i] = (poww[i-1]*base)%MOD;
        hashes[i] = (hashes[i-1]*base + ch)%MOD;
    }
    long long prev = 1;
    long long from = 1;
    long long last = s.size();
    long long endd = s.size();
    bool fl = false;
    while(from<last)
    {
        if(find_hash(prev,from)==find_hash(last,endd))
        {
            fl = false;
            ans+=2;
           // cout<<"  "<<from<<endl;
            prev = from+1;
            endd = last-1;
            from++;
            last--;
            continue;
        }
        fl = true;
        from++;
        last--;
    }
    if(fl||from==last)ans++;
    cout<<ans<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long t;
    cin>>t;
    while(t--)
        solve();
}

Compilation message (stderr)

palindromic.cpp: In function 'void solve()':
palindromic.cpp:22:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(i = 1; i<=s.size();i++)
      |                ~^~~~~~~~~~

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