Submission #859072

#	Time	Username	Problem	Language	Result	Execution time	Memory
859072		vuquangduoc1234	Palindromic Partitions (CEOI17_palindromic)	C++17	0 / 100	1 ms	4440 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 MOD = 1e9 + 7  ;
string s ;

int a[maxn] ,hashA[maxn] , Pow[maxn];

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



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;
      Pow[0] = 1;
      forin (i , 1 , n) Pow[i] = (Pow[i-1] * 26) % MOD;
      hashA[0] = 0;
      forin (i , 1 , n) hashA[i] = (hashA[i-1] * 26  + a[i] ) % MOD;

      int l = 1  , r = 1 , x = n , y = n  ;
      int ans = 0 ;
      while (true)
      {
          if (r == x || r > x)
          {
              ans ++ ;
              break ;
          }

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

    }

}

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