Submission #393316

#	Time	Username	Problem	Language	Result	Execution time	Memory
393316		rumen_m	Palindromic Partitions (CEOI17_palindromic)	C++17	0 / 100	1 ms	332 KiB

palindromic

# include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int base = 27;
const int maxn = 1e6+5;
int hashes[maxn];
int poww[maxn];
int find_hash(int from, int to)
{
    int pref = (hashes[from-1]*poww[to-from+1])%MOD;
    int ans = (hashes[to]+MOD-pref)%MOD;
    return ans;
}
void solve()
{
    string s;
    cin>>s;
    int ans = 0;
    poww[0] = 1;
    hashes[0] = 0;
    int i;
    for(i = 1; i<=s.size();i++)
    {
        int ch = s[i-1]-'a'+1;
        poww[i] = (poww[i-1]*base)%MOD;
        hashes[i] = (hashes[i-1]*base + ch)%MOD;
    }
    int prev = 1;
    int from = 1;
    int last = s.size();
    int 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);
    int 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: '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: 0 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40