Submission #934326

#	Time	Username	Problem	Language	Result	Execution time	Memory
934326		KaleemRazaSyed	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	374 ms	45868 KiB

palindromic

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int MAXN = 1e6+5, b = 193, mod1 = 1e9+7, mod2 = 1e9+9;

ll pw1[MAXN], pw2[MAXN], h1[MAXN], h2[MAXN];

pair<ll, ll> Hash(int l, int r)
{
  pair<ll, ll> res;
 res.first = (((h1[r + 1] - h1[l] * pw1[r - l + 1] % mod1) % mod1 + mod1)) % mod1;
 res.second= (((h2[r + 1] - h2[l] * pw2[r - l + 1] % mod2) % mod2 + mod2)) % mod2;
  return res;
}

void solve()
{
  string s;
  cin >> s;
  int ans = 0;
  int n = s.size();
  deque<int> idx[26];
  for(int i = 0; i < n; i ++)
    idx[s[i] - 'a'].push_back(i);

  h1[0] = h1[0] = 0;
  for(int i = 0; i < n; i ++)
    {
      h1[i + 1] = (h1[i] * b % mod1 + s[i]) % mod1;
      h2[i + 1] = (h2[i] * b % mod2 + s[i]) % mod2;
    }
  
  int l = 0, r = n-1;
  while(r - l + 1 > 0)
    {
      char c = s[l];
      while(idx[c - 'a'].front() < l) idx[c - 'a'].pop_front();
      while(idx[c - 'a'].back() > r) idx[c - 'a'].pop_back();
      
      int last = (int)idx[c - 'a'].size() - 1;
      while(last >= 0)
	{
	  int sz = r - idx[c-'a'][last] + 1;
	  //cerr << l << ' ' << l + sz - 1 << endl;
	  //cerr << r - sz + 1 << ' ' << r << endl;
	  if(Hash(l, l + sz - 1) == Hash(r - sz + 1, r) && sz * 2 <= r - l + 1)
	    {
	      ans += 2, l = l + sz, r = r - sz;
	      break;
	    }
	  last--;
	}
      if(last == -1)
	{
	  ans++;
	  break;
	}
    }
  cout << ans << endl;
}

int main()
{
  pw1[0] = pw2[0] = 1;
  for(int i = 1; i < MAXN; i++)
    pw1[i] = pw1[i - 1] * b % mod1,
      pw2[i] = pw2[i - 1] * b % mod2;
  int t;
  cin >> t;
  while(t--)
    solve();
  return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'void solve()':
palindromic.cpp:28:9: warning: operation on 'h1[0]' may be undefined [-Wsequence-point]
   28 |   h1[0] = h1[0] = 0;
      |   ~~~~~~^~~~~~~~~~~

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