oj.uz

Submission #934233

# Submission time Handle Problem Language Result Execution time Memory
934233 2024-02-27T03:05:35 Z Muhammad_Aneeq Palindromic Partitions (CEOI17_palindromic) C++17
0 / 100
 0 ms 344 KB 
/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
using namespace std;
#define int long long
int mod=1e9+7,base=997;
int power(int x,int y)
{
  int res=1;
  while (y)
  {
    if (y&1)
      res=(res*x)%mod;
    x=(x*x)%mod;
    y>>=1;
  }
  return res;
}
inline void solve()
{
  string s;
  cin>>s;
  int n=s.size();
  int hash[n+1]={};
  for (int i=0;i<n;i++)
    hash[i+1]=((hash[i]*base)+(s[i]-'a'+1))%mod;
  int l=0,r=1,l1=n-1,r1=n;
  int ans=0,len=0;
  while (r<l1)
  {
    len++;
    int f=(hash[l]*power(base,len))%mod;
    f=(hash[r]-f+mod)%mod;
    int g=(hash[l1]*power(base,len))%mod;
    g=(hash[r1]-g+mod)%mod;
    if (f==g)
    {
      ans+=2;
      l=r;
      r1=l1;
      len=0;
    }
    r++;
    l1--;
  }
  ans++;
  cout<<ans<<endl;
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    cin>>t;
    while (t--)
        solve();
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -