Submission #1118475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118475		VinhLuu	Palindromes (APIO14_palindrome)	C++17	100 / 100	880 ms	48296 KiB

palindrome

#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<ll, ll> pii;

const int N = 3e5 + 5;
const int M = 1e6 + 5;
const ll oo = 1e16;

int n, a[N];

int pos[N], sa[N], gap, tmp[N], lcp[N], LG[N], dp[22][N];
ll ans = 0;

bool cmp(int x,int y){
  if(pos[x] != pos[y]) return pos[x] < pos[y];
  x += gap;
  y += gap;
  return (x <= n && y <= n ? pos[x] < pos[y] : x > y);
}

void SA(){
  gap = 1;
  for(int i = 1; i <= n; i ++) pos[i] = a[i], sa[i] = i;
  while(true){
    sort(sa + 1, sa + n + 1, cmp);
    for(int i = 2; i <= n; i ++) tmp[i] = tmp[i - 1] + cmp(sa[i - 1], sa[i]);
    for(int i = 1; i <= n; i ++) pos[sa[i]] = tmp[i] + 1;
    if(tmp[n] == n - 1) break;
    gap = gap * 2;
  }


  for(int i = 1, k = 0; i <= n; i ++){
    if(pos[i] == n) continue;
    for(int j = sa[pos[i] + 1]; a[i + k] == a[j + k]; ) k ++;
    lcp[pos[i]] = k;
    if(k) k--;
  }

  for(int i = 1; i <= n; i ++) LG[i] = (i == 1 ? 0 : LG[i / 2] + 1);
  for(int i = n; i >= 1; i --){
    dp[0][i] = lcp[i];
    for(int j = 1; j <= 20 && i + (1 << j) - 1 <= n; j ++){
      dp[j][i] = min(dp[j - 1][i], dp[j - 1][i + (1 << (j - 1))]);
    }
  }
}

int kq[2][N];

namespace Hash{
  #define int long long
  mt19937 rd(2615367263);
  int ra(int l,int r){
    return l + rd() % (r - l + 1);
  }

  const int MOD[2] = {ra(1e9, 2e9), (int)1e9 + 7};
  const int base = 137;

  int pw[2][N], h[2][N], g[2][N];

  int get(int l,int r){
    int A = (h[0][r] + MOD[0] - h[0][l - 1] * pw[0][r - l + 1] % MOD[0]) % MOD[0];
    int B = (h[1][r] + MOD[1] - h[1][l - 1] * pw[1][r - l + 1] % MOD[1]) % MOD[1];
    return A * MOD[1] + B;
  }

  int rev(int l,int r){
    int A = (g[0][l] + MOD[0] - g[0][r + 1] * pw[0][r - l + 1] % MOD[0]) % MOD[0];
    int B = (g[1][l] + MOD[1] - g[1][r + 1] * pw[1][r - l + 1] % MOD[1]) % MOD[1];
    return A * MOD[1] + B;
  }

  void solve(){
    pw[0][0] = pw[1][0] = 1;
    for(int i = 1; i <= n; i ++) for(int j = 0; j <= 1; j ++){
      pw[j][i] = pw[j][i - 1] * base % MOD[j];
      h[j][i] = (h[j][i - 1] * base % MOD[j] + a[i]) % MOD[j];
    }

    for(int i = n; i >= 1; i --) for(int j = 0; j <= 1; j ++) {
      g[j][i] = (g[j][i + 1] * base % MOD[j] + a[i]) % MOD[j];
    }

    for(int i = 1; i <= n; i ++){
      int l = 1, r = min(n - i, i);
      while(l <= r) {
        int mid = (l + r) / 2;
        if(get(i - mid + 1, i) == rev(i + 1, i + mid)){
          kq[0][i] = mid;
          l = mid + 1;
        }else r = mid - 1;
      }

      l = 1, r = min(n - i + 1, i);
      while(l <= r) {
        int mid = (l + r) / 2;
//        if(i == 4) {
//          cerr << i - mid + 1 << " " << i << " " << get(i - mid + 1, i) << " h\n";
//          cerr << i << " " << i + mid - 1
//        }
        if(get(i - mid + 1, i) == rev(i, i + mid - 1)){
          kq[1][i] = mid;
          l = mid + 1;
        }else r = mid - 1;
      }
    }
  }
}

int query(int l,int r){
  int k = LG[r - l + 1];
  return min(dp[k][l], dp[k][r - (1 << k) + 1]);
}

int bs(int x, int len){
  int i = pos[x];
  int l = 1, r = i - 1, _left = i;
  while(l <= r){
    int mid = (l + r) / 2;
    if(query(mid, i - 1) >= len){
      _left = mid;
      r = mid - 1;
    }else l = mid + 1;
  }
  l = i, r = n - 1;
  int _right = i;
  while(l <= r) {
    int mid = (l + r) / 2;
    if(query(i, mid) >= len){
      _right = mid + 1;
      l = mid + 1;
    }else r = mid - 1;
  }
  return _right - _left + 1;
}


signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  string s; cin >> s;
  n = s.size(); s = " " + s;
  for(int i = 1; i <= n; i ++) a[i] = (int)(s[i] - 'a') + 1;

  SA();

  Hash :: solve();

  for(int i = 1; i <= n; i ++){
    if(kq[0][i]){
      int tmp = bs(i - kq[0][i] + 1, 2 * kq[0][i]);
      ans = max(ans, 1ll * tmp * 2 * kq[0][i]);
    }
    if(kq[1][i]){
      int tmp = bs(i - kq[1][i] + 1, 2 * kq[1][i] - 1);
      ans = max(ans, 1ll * tmp * (2 * kq[1][i] - 1));
    }
  }
  cout << ans;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:153:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:154:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27