답안 #96693 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96693	2019-02-11T04:03:16 Z	fjchf02	회문 (APIO14_palindrome)	C++	73 / 100	1000 ms	29432 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];

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 = 19; i >= 0; i--) {
      int nx = l - (1 << i);
      if (nx >= 0 && lcp[i][nx] >= len) {
        l = nx;
      }
    }
  }
  {
    for (int i = 19; 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() {
  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:102: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	2 ms	504 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	380 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct
21	Correct	2 ms	376 KB	Output is correct
22	Correct	2 ms	376 KB	Output is correct
23	Correct	2 ms	376 KB	Output is correct
24	Correct	2 ms	376 KB	Output is correct
25	Correct	2 ms	376 KB	Output is correct
26	Correct	2 ms	376 KB	Output is correct
27	Correct	2 ms	376 KB	Output is correct
28	Correct	2 ms	348 KB	Output is correct
29	Correct	2 ms	376 KB	Output is correct
30	Correct	2 ms	380 KB	Output is correct
31	Correct	2 ms	376 KB	Output is correct
32	Correct	2 ms	376 KB	Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

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

Subtask #4
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	38 ms	9336 KB	Output is correct
2	Correct	39 ms	9464 KB	Output is correct
3	Correct	53 ms	9400 KB	Output is correct
4	Correct	50 ms	9464 KB	Output is correct
5	Correct	133 ms	9596 KB	Output is correct
6	Correct	74 ms	9464 KB	Output is correct
7	Correct	60 ms	9464 KB	Output is correct
8	Correct	30 ms	9464 KB	Output is correct
9	Correct	58 ms	9592 KB	Output is correct
10	Correct	150 ms	9496 KB	Output is correct

Subtask #5
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	134 ms	29432 KB	Output is correct
2	Correct	132 ms	29300 KB	Output is correct
3	Correct	159 ms	29304 KB	Output is correct
4	Correct	160 ms	29176 KB	Output is correct
5	Execution timed out	1066 ms	27840 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

답안 #96693

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 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
0 / 27.0