Submission #230589

#	Time	Username	Problem	Language	Result	Execution time	Memory
230589		AlexLuchianov	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	620 ms	66820 KiB

palindromic

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 1000000;
int const sigma = 26;
int const modulo = 1000000007;
int const modulo2 = 998244353;
int pw[2][1 + nmax];

void computepow(){
  pw[0][0] = pw[1][0] = 1;
  for(int i = 1; i <= nmax; i++){
    pw[0][i] = 1LL * pw[0][i - 1] * sigma % modulo;
    pw[1][i] = 1LL * pw[1][i - 1] * sigma % modulo2;
  }
}

class Hash{
public:
  int l;
  int number;
  int number2;
  Hash(char ch = 0){
    if(ch == 0){
      l = 0;
      number = number2 = 0;
    } else {
      l = 1;
      number = ch - 'a';
      number2 = ch - 'a';
    }
  }
  Hash operator + (Hash const &a) const {
    Hash result;
    result.l = l + a.l;
    result.number = (1LL * number * pw[0][a.l] + a.number) % modulo;
    result.number2 = (1LL * number2 * pw[1][a.l] + a.number2) % modulo2;
    return result;
  }
  bool operator == (Hash const &a) const {
    return l == a.l && number == a.number && number2 == a.number2;
  }
};
string s;

int _partition(int from, int to){
  if(to < from)
    return 0;
  Hash f1, f2;
  int d = (to - from + 1);
  for(int i = 1; i * 2 <= d; i++){
    f1 = f1 + s[from];
    from++;
    f2 = Hash(s[to]) + f2;
    to--;

    if(f1 == f2)
      return _partition(from, to) + 2;
  }
  return 1;
}

int solve(){
  cin >> s;
  s = "#" + s;
  int n = s.size() - 1;
  return _partition(1, n);
}

int main()
{
  computepow();
  int t;
  cin >> t;
  for(int testcase = 1; testcase <= t; testcase++)
    cout << solve() << '\n';
  return 0;
}

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