Submission #859214

#	Time	Username	Problem	Language	Result	Execution time	Memory
859214		vuquangduoc1234	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	295 ms	48120 KiB

palindromic

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define forin(i , a , b ) for (int i = (a) ; i <= (b) ; i ++)
#define pb push_back

const int maxn = 1e6 + 100 ;
const int mod1 = 1e9 + 7 ;
const int mod2 = 1e6 + 7 ;
string s ;

int a[maxn] ,hashA[maxn] , Pow1[maxn];
int hashB[maxn] , Pow2[maxn];

long long getHashA(int i, int j)
{
    return ((hashA[j] - hashA[i-1] * Pow1[j-i+1]) % mod1 + mod1) % mod1;
}

long long getHashB(int i, int j)
{
    return ((hashB[j] - hashB[i-1] * Pow2[j-i+1]) % mod2 + mod2) % mod2;
}



signed main ()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int tt;
    cin >> tt;
    while (tt--)
    {
      string s;
      cin >> s ;
      s = '!' + s ;
      int n = s.size() - 1 ;
      forin(i , 1 , n)
       a[i] = s[i] - 'a' + 1;
      Pow1[0] = Pow2[0] = 1;
      forin (i  , 1 , n) Pow1[i] = (Pow1[i-1] * 300) % mod1;
      forin (i  , 1 , n) Pow2[i] = (Pow2[i-1] * 300) % mod2;
      hashA[0] = hashB[0] = 0;
      forin (i, 1 , n) hashA[i] = (hashA[i-1] * 300 + a[i]) % mod1;
      forin (i, 1 , n) hashB[i] = (hashB[i-1] * 300 + a[i]) % mod2;

      int l = 1  , r = 1 , x = n , y = n  ;
      int ans = 0 ;
      while (l <= x)
      {
          if (r >= x && l <= x)
          {
              //cout << l << " " << x << endl;
              ans ++ ;
              break ;
          }

          if (getHashA(l , r) == getHashA(x,y) && getHashB(l , r) == getHashB(x,y))
          {
              ans+=2;
              r ++;
              l = r ;
              x --;
              y = x ;
          }
          else
          {
              r++;
              x--;
          }
      }
      cout << ans   << "\n";
      forin(i,1,n) Pow1[i] = hashA[i] = hashB[i] = Pow2[i] = a[i] =  0 ;

    }

}

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