Submission #869247

#	Time	Username	Problem	Language	Result	Execution time	Memory
869247		LOLOLO	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	67 ms	28440 KiB

palindromic

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

const int N = 1e6 + 5;
const int BASE = 37;

long long haha[N];
long long hihi[N];

long long kkk(int L, int R)
{
  return haha[R] - haha[L - 1] * hihi[R - L + 1];
}

void solve()
{
  string s;
  cin >> s;

  int n = s.size();
  s = ' ' + s;

  for (int i = 1; i <= n; i++)
    haha[i] = haha[i - 1] * BASE + s[i] - 'a' + 1;

  int l = 1, r = n;
  int ahihi = 1, orz = n;
  long long hjhj, hehe;
  int ans = 0;

  while (l < r)
  {
    hjhj = kkk(ahihi, l);
    hehe = kkk(r, orz);
    if (hjhj == hehe)
    {
      ahihi = l + 1,
      orz = r - 1;
      ans += 2;
      hjhj = 0, hehe = 0;
    }
    l++;
    r--;
  }

  cout << ans + (l == r || hjhj != hehe) << "\n";
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  hihi[0] = 1;
  for (int i = 1; i < N; i++)
    hihi[i] = hihi[i - 1] * BASE;

  int t;
  cin >> t;

  while (t--)
    solve();

  return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'void solve()':
palindromic.cpp:46:33: warning: 'hehe' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |   cout << ans + (l == r || hjhj != hehe) << "\n";
      |                            ~~~~~^~~~~~~
palindromic.cpp:46:33: warning: 'hjhj' may be used uninitialized in this function [-Wmaybe-uninitialized]

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