제출 #1082144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1082144		juicy	Palinilap (COI16_palinilap)	C++17	100 / 100	181 ms	25812 KiB

palinilap

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
mt19937 rng(69420);

bool check(int x) {
  for (int i = 2; i * i <= x; ++i) {
    if (x % i == 0) {
      return 1;
    }
  }
  return 0;
}

int prime(int s, int e) {
  int x = rng() % (e - s + 1) + s;
  while (!check(x)) {
    --x;
  }
  return x;
}

using T = array<int, 3>;

const int N = 1e5 + 5;
T M = {prime(1e8, 1e9), prime(1e8, 1e9), prime(1e8, 1e9)}, B = {prime(1000, 10000), prime(1000, 10000), prime(1000, 10000)};

int n;
int cnt[N], h[3][N], rh[3][N], pw[3][N];
long long f[N];
array<long long, 26> c[N];
string s;
 
int qry(int l, int r, int *h, int M, int *pw) {
  return ((h[r] - (long long) h[l - 1] * pw[r - l + 1]) % M + M) % M;
}

array<int, 3> qry(int l, int r, int h[3][N]) {
  array<int, 3> res{};
  for (int i = 0; i < 3; ++i) {
    res[i] = qry(l, r, h[i], M[i], pw[i]);
  }
  return res;
}
 
int find(int s, int e) {
  if (s < 1 || e > n) {
    return 0;
  }
  int l = 1, r = min(s, n - e + 1), res = 0;
  while (l <= r) {
    int m = (l + r) / 2;
    if (qry(s - m + 1, s, h) == qry(n - e - m + 2, n - e + 1, rh)) {
      res = m;
      l = m + 1;
    } else {
      r = m - 1;
    }
  }
  return res;
}
 
template<class T>
void upd(int s, int e, int x, T *f) {
  f[s] += x;
  f[e + 1] -= x; 
}
 
signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
 
  cin >> s;
  n = s.size();
  for (int j = 0; j < 3; ++j) {
    pw[j][0] = 1;
    for (int i = 0; i < n; ++i) {
      pw[j][i + 1] = (long long) pw[j][i] * B[j] % M[j];
      h[j][i + 1] = ((long long) h[j][i] * B[j] + s[i] - 'a' + 1) % M[j];
    }
  }
  for (int j = 0; j < 3; ++j) {
    for (int i = n - 1; i >= 0; --i) {
      rh[j][i + 1] = ((long long) rh[j][i + 2] * B[j] + s[i] - 'a' + 1) % M[j];
    }
    reverse(rh[j] + 1, rh[j] + n + 1);
  }
  long long res = 0;
  for (int i = 1; i < n; ++i) {
    int l = find(i, i + 1);
    res += l;
    int L = i - l + 1, R = i + l;
    if (l > 0) {
      upd(i + 1, i + l, 1, cnt);
      upd(i + 1, i + l, -R - 1, f);
      upd(i - l + 1, i, -1, cnt);
      upd(i - l + 1, i, L - 1, f);
    }
    if (1 < L && R < n) {
      int l = find(L - 2, R + 2);
      c[L - 1][s[R] - 'a'] += l + 1;
      c[R + 1][s[L - 2] - 'a'] += l + 1;
    }
  }
  for (int i = 1; i <= n; ++i) {
    int l = find(i - 1, i + 1) + 1;
    res += l;
    int L = i - l + 1, R = i + l - 1;
    if (l > 1) {
      upd(L, i - 1, -1, cnt);
      upd(L, i - 1, L - 1, f);
      upd(i + 1, R, 1, cnt);
      upd(i + 1, R, -R - 1, f);
    }
    if (1 < L && R < n) {
      int l = find(L - 2, R + 2);
      c[L - 1][s[R] - 'a'] += l + 1;
      c[R + 1][s[L - 2] - 'a'] += l + 1;
    }
  }
  long long ma = 0;
  for (int i = 1; i <= n; ++i) {
    cnt[i] += cnt[i - 1];
    f[i] += f[i - 1];
    long long delta = (long long) cnt[i] * i + f[i];
    for (int j = 0; j < 26; ++j) {
      ma = max(ma, delta + c[i][j]);
    }
  }
  cout << res + ma;
  return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 37 / 37
• Subtask 3: 46 / 46