답안 #96694 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96694	2019-02-11T04:05:30 Z	fjchf02	회문 (APIO14_palindrome)	C++	100 / 100	911 ms	30712 KB

palindrome

#include <bits/stdc++.h>

using namespace std;

const int N = 300010;

int n;
char s[N];
int a[N], gr[N], new_gr[N], ptr_gr[N], st[N], lcp[20][N];
int res[2 * N];
int l2[N];

bool cmp(int i, int j) {
  return s[i] < s[j];
}

void calc() {
  for (int i = 0; i < n; i++) {
    a[i] = i;
  }
  sort(a, a + n, cmp);
  gr[a[0]] = 0;
  for (int i = 1; i < n; i++) {
    gr[a[i]] = gr[a[i - 1]] + (s[a[i - 1]] != s[a[i]]);
  }
  int cnt = gr[a[n - 1]] + 1;
  int step = 1;
  while (cnt < n) {
    int ptr = 0;
    for (int i = n - step; i < n; i++) {
      st[ptr++] = i;
    }
    for (int i = 0; i < n; i++) {
      if (a[i] >= step) {
        st[ptr++] = a[i] - step;
      }
    }
    for (int i = n - 1; i >= 0; i--) {
      ptr_gr[gr[a[i]]] = i;
    }
    for (int i = 0; i < n; i++) {
      int x = st[i];
      a[ptr_gr[gr[x]]++] = x;
    }
    new_gr[a[0]] = 0;
    for (int i = 1; i < n; i++) {
      if (gr[a[i]] != gr[a[i - 1]]) {
        new_gr[a[i]] = new_gr[a[i - 1]] + 1;
      } else {
        int pre = (a[i - 1] + step < n ? gr[a[i - 1] + step] : -1);
        int cur = (a[i] + step < n ? gr[a[i] + step] : -1);
        new_gr[a[i]] = new_gr[a[i - 1]] + (pre != cur);
      }
    }
    copy(new_gr, new_gr + n, gr);
    cnt = gr[a[n - 1]] + 1;
    step <<= 1;
  }
  int k = 0;
  for (int i = 0; i < n; i++) {
    if (gr[i] == n - 1) {
      k = 0;  
    } else {
      k = max(0, k - 1);
      int j = a[gr[i] + 1];
      while (i + k < n && j + k < n && s[i + k] == s[j + k]) {
        k++;
      }
      lcp[0][gr[i]] = k;
    }
  }
  for (int k = 0; k < 19; k++) {
    int len = 1 << k;
    for (int i = 0; i + 2 * len - 1 < n - 1; i++) {
      lcp[k + 1][i] = min(lcp[k][i], lcp[k][i + len]);
    }
  }
}

int solve(int x, int len) {
  x = gr[x];
  int l = x, r = x - 1;
  {
    for (int i = l2[l + 1]; i >= 0; i--) {
      int nx = l - (1 << i);
      if (nx >= 0 && lcp[i][nx] >= len) {
        l = nx;
      }
    }
  }
  {
    for (int i = l2[n - x + 2]; i >= 0; i--) {
      int nx = r + (1 << i);
      if (nx < n - 1 && lcp[i][r + 1] >= len) {
        r = nx;
      }
    }
  }
  return r - l + 2;
}

int main() {
  for (int i = 2; i < N; i++) {
    l2[i] = l2[i >> 1] + 1;
  }
  scanf("%s", s);
  n = strlen(s);
  calc();
  int cnt[26];
  fill(cnt, cnt + 26, 0);
  for (int i = 0; i < n; i++) {
    cnt[int(s[i] - 'a')]++;
  }
  long long ans = *max_element(cnt, cnt + 26);
  int l = -1, r = -1;
  for (int z = 0; z < 2 * n - 1; z++) {
    int i = (z + 1) >> 1;
    int j = z >> 1;
    int& p = res[z];
    p = (i >= r ? 0 : min(r - i, res[2 * (l + r) - z]));
    int pre = res[2 * (l + r) - z];
    while (i - p - 1 >= 0 && j + p + 1 < n && s[i - p - 1] == s[j + p + 1]) {
      p++;
      if (p > pre) {
        int len = 2 * p + (z % 2 == 0);
        int last = i - p;
        ans = max(ans, (long long) len * solve(last, len));
      }
    }
    if (j + p > r) {
      l = i - p;
      r = j + p;
    }
  }
  printf("%lld\n", ans);
  return 0;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s);
   ~~~~~^~~~~~~~~

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1528 KB	Output is correct
2	Correct	3 ms	1528 KB	Output is correct
3	Correct	3 ms	1528 KB	Output is correct
4	Correct	3 ms	1528 KB	Output is correct
5	Correct	3 ms	1528 KB	Output is correct
6	Correct	3 ms	1528 KB	Output is correct
7	Correct	3 ms	1528 KB	Output is correct
8	Correct	3 ms	1532 KB	Output is correct
9	Correct	3 ms	1612 KB	Output is correct
10	Correct	3 ms	1532 KB	Output is correct
11	Correct	3 ms	1528 KB	Output is correct
12	Correct	3 ms	1528 KB	Output is correct
13	Correct	3 ms	1528 KB	Output is correct
14	Correct	2 ms	1528 KB	Output is correct
15	Correct	3 ms	1528 KB	Output is correct
16	Correct	3 ms	1528 KB	Output is correct
17	Correct	3 ms	1528 KB	Output is correct
18	Correct	3 ms	1528 KB	Output is correct
19	Correct	3 ms	1656 KB	Output is correct
20	Correct	3 ms	1528 KB	Output is correct
21	Correct	3 ms	1656 KB	Output is correct
22	Correct	3 ms	1700 KB	Output is correct
23	Correct	3 ms	1528 KB	Output is correct
24	Correct	3 ms	1656 KB	Output is correct
25	Correct	3 ms	1528 KB	Output is correct
26	Correct	3 ms	1528 KB	Output is correct
27	Correct	3 ms	1528 KB	Output is correct
28	Correct	3 ms	1528 KB	Output is correct
29	Correct	3 ms	1528 KB	Output is correct
30	Correct	3 ms	1628 KB	Output is correct
31	Correct	3 ms	1656 KB	Output is correct
32	Correct	3 ms	1656 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1656 KB	Output is correct
2	Correct	3 ms	1656 KB	Output is correct
3	Correct	3 ms	1660 KB	Output is correct
4	Correct	3 ms	1656 KB	Output is correct
5	Correct	4 ms	1656 KB	Output is correct
6	Correct	3 ms	1656 KB	Output is correct
7	Correct	3 ms	1656 KB	Output is correct
8	Correct	4 ms	1656 KB	Output is correct
9	Correct	3 ms	1656 KB	Output is correct
10	Correct	4 ms	1656 KB	Output is correct
11	Correct	3 ms	1656 KB	Output is correct
12	Correct	4 ms	1656 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	2424 KB	Output is correct
2	Correct	5 ms	2424 KB	Output is correct
3	Correct	5 ms	2424 KB	Output is correct
4	Correct	5 ms	2424 KB	Output is correct
5	Correct	8 ms	2424 KB	Output is correct
6	Correct	7 ms	2424 KB	Output is correct
7	Correct	5 ms	2424 KB	Output is correct
8	Correct	5 ms	2424 KB	Output is correct
9	Correct	5 ms	2424 KB	Output is correct
10	Correct	9 ms	2428 KB	Output is correct

Subtask #4
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	10460 KB	Output is correct
2	Correct	40 ms	10488 KB	Output is correct
3	Correct	34 ms	10488 KB	Output is correct
4	Correct	36 ms	10488 KB	Output is correct
5	Correct	106 ms	10536 KB	Output is correct
6	Correct	69 ms	10616 KB	Output is correct
7	Correct	52 ms	10528 KB	Output is correct
8	Correct	29 ms	10500 KB	Output is correct
9	Correct	53 ms	10584 KB	Output is correct
10	Correct	92 ms	10744 KB	Output is correct

Subtask #5
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	124 ms	30172 KB	Output is correct
2	Correct	129 ms	30172 KB	Output is correct
3	Correct	108 ms	30200 KB	Output is correct
4	Correct	110 ms	30044 KB	Output is correct
5	Correct	911 ms	30108 KB	Output is correct
6	Correct	177 ms	30712 KB	Output is correct
7	Correct	209 ms	30584 KB	Output is correct
8	Correct	98 ms	30288 KB	Output is correct
9	Correct	98 ms	30304 KB	Output is correct
10	Correct	819 ms	30584 KB	Output is correct
11	Correct	148 ms	30508 KB	Output is correct
12	Correct	191 ms	30584 KB	Output is correct

답안 #96694

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 15.0 / 15.0

Subtask #3 24.0 / 24.0

Subtask #4 26.0 / 26.0

Subtask #5 27.0 / 27.0

Subtask #1
8.0 / 8.0

Subtask #2
15.0 / 15.0

Subtask #3
24.0 / 24.0

Subtask #4
26.0 / 26.0

Subtask #5
27.0 / 27.0