Submission #35814

#	Time	Username	Problem	Language	Result	Execution time	Memory
35814		funcsr	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	443 ms	9844 KiB

palindromic

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(xs) xs.begin(), xs.end()
using namespace std;
const int H = 12345;
const int MOD = 1000000007;

int pH[1000001];
int solve(string S) {
  int N = S.length();
  int lo = 0, hi = N-1;
  int a = 0, b = 0, n = 0, s = 0;
  while (lo < hi) {
    a = (1LL*a*H + S[lo++]) % MOD;
    b = (1LL*pH[n]*S[hi--] + b) % MOD;
    n++;
    if (a == b) a = 0, b = 0, n = 0, s += 2;
  }
  if (lo == hi) s++;
  else if (n > 0) s++;
  return s;
}

int T;
signed main() {
  pH[0] = 1;
  for (int i=1; i<=1000000; i++) pH[i] = (1LL*pH[i-1]*H)%MOD;

  cin >> T;
  rep(_, T) {
    string S;
    cin >> S;
    cout << solve(S) << "\n";
  }
  return 0;
}

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