Submission #593769

#	Time	Username	Problem	Language	Result	Execution time	Memory
593769		cadmiumsky	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	398 ms	50116 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int nmax = 1e6 + 5;

#define int ll
#define hash mamamare
const int mod = 998244853;
int p[nmax][2];

struct hash {
  int v[2], len;
  hash() {v[0] = v[1] = len = 0; }
  hash(char ch) {v[0] = v[1] = ch - 'a', len = 1;}
  hash(int a, int b, int c) {v[0] = a, v[1] = b, len = c; }
  hash operator + (const hash& other) {
    return hash((v[0] * p[other.len][0] + other.v[0]) % mod, 
                (v[1] * p[other.len][1] + other.v[1]) % mod,
                 len + other.len);
  }
  hash operator - (const hash& other) {
    return hash((v[0] - p[len - other.len][0] * other.v[0] % mod + mod) % mod,
                (v[1] - p[len - other.len][1] * other.v[1] % mod + mod) % mod,
                len - other.len);
  }
  bool operator == (const hash& other) {
    return tuple<int,int,int>{v[0], v[1], len} == tuple<int,int,int>{other.v[0], other.v[1], other.len};
  }
};
#undef int

void testcase() {
  string s;
  int n;
  cin >> s;
  n = s.size();
  s = "$" + s;
  vector<hash> vec(n + 1);
  for(int i = 1; i <= n; i++)
    vec[i] = vec[i - 1] + hash(s[i]);
  auto gethash = [&](int l, int r) {
    return vec[r] - vec[l - 1];
  };
  int l = 1, r = n, len = 0, cnt = 0;
  while(l < r) {
    len++;
    if(gethash(l - len + 1, l) == gethash(r, r + len - 1)) {
      cnt += 2;
      //cerr << gethash(l - len + 1, l).v[0] << ' ' << l - len + 1 << ' ' << l << '\t' << r  << ' ' << r + len - 1 << '\n';
      len = 0;
      
    }
    l++;
    r--;
  }
  if(len != 0 || l == r)
    cnt++;
  cout << cnt << '\n';
}
 

int main() {
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  //mt19937 rng(69420);
  p[0][1] = p[0][0] = 1;
  p[1][1] = rng() % (mod - 5) + 3;
  p[1][0] = rng() % (mod - 5) + 3;
  for(int i = 2; i < nmax; i++)
    p[i][0] = p[i - 1][0] * p[1][0] % mod,
    p[i][1] = p[i - 1][1] * p[1][1] % mod;
  //cerr << p[1][1] << ' ' << p[1][0] << '\n';
  //cerr << p[2][1] << ' ' << p[2][0] << '\n';
  int t;
  cin >> t;
  while(t--)
    testcase();
}

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