Submission #69699

#	Time	Username	Problem	Language	Result	Execution time	Memory
69699		Googal	Palindromic Partitions (CEOI17_palindromic)	C++14	60 / 100	6 ms	1960 KiB

palindromic

#include <iostream>
#include <cstring>

using namespace std;

typedef long long ll;

const ll NMAX = 1e4;
const ll MOD = 1e9;
const ll base = 26;

ll t, n;
ll mult[1 + NMAX];
ll phash[1 + NMAX];

char s[NMAX + 10];

ll solve_hash(ll le, ll ri) {
  return (phash[ri] - phash[le - 1] * mult[ri - le + 1] + MOD * MOD) % MOD;
}

void compute_mult() {
  mult[0] = 1;

  for(ll i = 1; i <= NMAX; i++)
    mult[i] = mult[i - 1] * base % MOD;
}

int main()
{
  ios_base::sync_with_stdio(false);
  compute_mult();

  cin >> t;

  for(ll test = 1; test <= t; test++) {
    cin >> (s + 1);
    n = strlen(s + 1);

    for(ll i = 1; i <= n; i++)
      phash[i] = (phash[i - 1] * base + s[i]) % MOD;

    ll le = 1;
    ll ri = n;
    ll res = 0;

    while(le <= ri) {
      ll len = 1;

      while(le + len - 1 < ri - len + 1 && solve_hash(le, le + len - 1) != solve_hash(ri - len + 1, ri))
        len++;

      if(le + len - 1 >= ri - len + 1) {
        res++;
        break;
      }

      res += 2;
      le += len;
      ri -= len;
    }

    cout << res << '\n';
  }
}

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