oj.uz

Submission #859072

# Submission time Handle Problem Language Result Execution time Memory
859072 2023-10-09T16:15:49 Z vuquangduoc1234 Palindromic Partitions (CEOI17_palindromic) C++17
0 / 100
 1 ms 4440 KB 
#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.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

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