oj.uz

Submission #859214

# Submission time Handle Problem Language Result Execution time Memory
859214 2023-10-10T01:40:31 Z vuquangduoc1234 Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 295 ms 48120 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 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10684 KB Output is correct
5 Correct 1 ms 10584 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10684 KB Output is correct
5 Correct 1 ms 10584 KB Output is correct
6 Correct 1 ms 10584 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10684 KB Output is correct
5 Correct 1 ms 10584 KB Output is correct
6 Correct 1 ms 10584 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 4 ms 10844 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 4 ms 10844 KB Output is correct
13 Correct 3 ms 10696 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10684 KB Output is correct
5 Correct 1 ms 10584 KB Output is correct
6 Correct 1 ms 10584 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 4 ms 10844 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 4 ms 10844 KB Output is correct
13 Correct 3 ms 10696 KB Output is correct
14 Correct 295 ms 48120 KB Output is correct
15 Correct 151 ms 44492 KB Output is correct
16 Correct 263 ms 46796 KB Output is correct
17 Correct 157 ms 35644 KB Output is correct