제출 #882923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
882923		nguyentunglam	Palindromes (APIO14_palindrome)	C++17	73 / 100	1064 ms	29216 KiB

palindrome

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;

const int N = 3e5 + 10;

const long long base = 31, mod = 1e9 + 7;

long long f[N], g[N], p[N];

int pos[N], sa[N], tmp[N], last[N], pre[N], nxt[N], gap;

vector<int> event[N];

string s;

int get (int l, int r) {
  return (f[r] - f[l - 1] * p[r - l + 1] + mod * mod) % mod;
}

int _get(int l, int r) {
  return (g[l] - g[r + 1] * p[r - l + 1] + mod * mod) % mod;
}

int lcp (int x, int y) {
  int l = 1, r = min(last[x], last[y]), last = 0;
  while (l <= r) {
    int mid = l + r >> 1;
    if (get(x, x + mid - 1) == get(y, y + mid - 1)) {
      last = mid;
      l = mid + 1;
    } else r = mid - 1;
  }
  return last;
}

bool cmp (int x, int y) {
  int len = lcp(x, y);
  if (len == min(last[x], last[y])) return last[x] < last[y];
  return s[x + len] < s[y + len];
}

int32_t main() {
  #define task ""

  cin.tie(0) -> sync_with_stdio(0);

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

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

  cin >> s; s = " " + s;

  int n = s.size() - 1;

  p[0] = 1;
  for(int i = 1; i <= n; i++) {
    p[i] = p[i - 1] * base % mod;
    f[i] = (f[i - 1] * base + s[i] - 'a' + 1) % mod;
  }

  for(int i = n; i >= 1; i--) {
    g[i] = (g[i + 1] * base + s[i] - 'a' + 1) % mod;
  }

  auto calc = [&] (int k) {
    long long ret = 0;
    int _n = 0;
    for(int i = 1; i <= n; i++) sa[i] = i;

    sort(sa + 1, sa + n + 1, cmp);

    for(int i = 1; i <= n; i++) {
      ret = max(ret, 2LL * last[i] + k);
      pre[i] = i - 1;
      nxt[i] = i + 1;
      if (i < n) event[lcp(sa[i], sa[i + 1])].push_back(i);
    }

    for(int i = n; i >= 1; i--) {
      for(int &j : event[i]) {
        int l = pre[j], r = nxt[j];
        ret = max(ret, 1LL * (r - l) * (2 * i + k));
        nxt[l] = r; pre[r] = l;
      } event[i].clear();
    }
    return ret;
  };

  for(int i = 1; i <= n; i++) {
    int l = 1, r = min(i, n - i + 1);
    last[i] = 0;
    while (l <= r) {
      int mid = l + r >> 1;
      if (get(i - mid + 1, i) == _get(i, i + mid - 1)) {
        last[i] = mid;
        l = mid + 1;
      } else r = mid - 1;
    }
  }

  long long ans1 = calc(-1);

//  cout << ans1;

  for(int i = 1; i <= n; i++) {
    int l = 1, r = min(i - 1, n - i + 1);
    last[i] = 0;
    while (l <= r) {
      int mid = l + r >> 1;
      if (get(i - mid, i - 1) == _get(i, i + mid - 1)) {
        last[i] = mid;
        l = mid + 1;
      } else r = mid - 1;
    }
  }

  long long ans2 = calc(0);

  cout << max(ans1, ans2);
}

컴파일 시 표준 에러 (stderr) 메시지

palindrome.cpp: In function 'int lcp(int, int)':
palindrome.cpp:29:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid = l + r >> 1;
      |               ~~^~~
palindrome.cpp: In lambda function:
palindrome.cpp:75:9: warning: unused variable '_n' [-Wunused-variable]
   75 |     int _n = 0;
      |         ^~
palindrome.cpp: In function 'int32_t main()':
palindrome.cpp:101:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |       int mid = l + r >> 1;
      |                 ~~^~~
palindrome.cpp:117:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  117 |       int mid = l + r >> 1;
      |                 ~~^~~
palindrome.cpp:50:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     freopen("task.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:51:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     freopen("task.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:55:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     freopen (task".inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:56:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     freopen (task".out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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