Submission #841817

#	Time	Username	Problem	Language	Result	Execution time	Memory
841817		WLZ	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	67 ms	12816 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
 
const int MOD = (int) 1e9 + 7;
const int p = 31;
 
/** Assumes 1 <= a, b < MOD */
int add(int a, int b) {
  if (a + b >= MOD) return a + b - MOD;
  return a + b;
}
 
/** Assumes 1 <= a, b < MOD */
int sub(int a, int b) {
  return add(a, MOD - b);
}
 
/** Assumes 1 <= a, b < MOD */
int mul(int a, int b) {
  return (long long) a * b % MOD;
}
 
/** Assumes 1 <= b < MOD */
int modpow(int b, int p) {
  if (p == 0) return 1;
  int ans = modpow(mul(b, b), p / 2);
  if (p % 2 == 1) ans = mul(ans, b);
  return ans;
}
 
int extgcd(int a, int b, int &x, int &y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  int x1, y1, g = extgcd(b, a % b, x1, y1);
  x = y1; y = sub(x1, mul(y1, (a / b) % MOD));
  return g;
}
 
/** Assumes gcd(x, MOD) = 1 */ 
int inv(int x) {
  int x1, y1;
  extgcd(x, MOD, x1, y1);
  return x1;
}
 
void solve() {
  string s;
  cin >> s;
  int n = (int) s.length();
  int ans = 0;
  int l = 0, r = n - 1;
  while (l <= r) {
    bool found = false;
    int l_hash = 0, r_hash = 0, pw = 1;
    for (int i = l, j = r; i < j; i++, j--) {
      l_hash = add(mul(p, l_hash), s[i] - 'a' + 1);
      r_hash = add(r_hash, mul(pw, s[j] - 'a' + 1));
      pw = mul(pw, p);
      if (l_hash == r_hash && s.substr(l, i - l + 1) == s.substr(j, r - j + 1)) {
        found = true;
        l = i + 1; r = j - 1;
        break;
      }
    }
    if (!found) {
      ans++;
      break;
    }
    ans += 2;
  }
  cout << ans << '\n';
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}

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