oj.uz

답안 #486546

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
486546 2021-11-12T01:10:35 Z rainboy Palinilap (COI16_palinilap) C
100 / 100
 330 ms 28008 KB 
#include <stdio.h>
#include <string.h>

#define N	100000
#define N_	(N * 2 + 1)
#define A	26

int min(int a, int b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

char cc_[N_ + 1]; int aa0[N_], aa1[N_], sa[N_], pp[N_], st[N_ * 2], n_;

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (aa0[ii[j]] == aa0[i_])
				j++;
			else if (aa0[ii[j]] < aa0[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

void compress() {
	int i, a;

	for (i = 0, a = 0; i < n_; i++)
		aa0[sa[i]] = i + 1 == n_ || aa0[sa[i + 1]] != aa0[sa[i]] || aa1[sa[i + 1]] != aa1[sa[i]] ? a++ : a;
}

void extend(int m) {
	int i;

	for (i = 0; i < n_; i++)
		aa1[i] = i + m < n_ ? aa0[i + m] : -1;
}

void sort_(int *aa, int *ii, int *jj) {
	static int kk[N_ + 2];
	int i, j, a;

	memset(kk, 0, (n_ + 2) * sizeof *kk);
	for (i = 0; i < n_; i++) {
		a = aa[i] + 1;
		kk[a + 1]++;
	}
	for (a = 1; a <= n_ + 1; a++)
		kk[a] += kk[a - 1];
	for (i = 0; i < n_; i++) {
		j = ii[i], a = aa[j] + 1;
		jj[kk[a]++] = j;
	}
}

void build() {
	int m, i, j, a, p;

	for (i = 0; i < n_; i++) {
		sa[i] = i;
		aa0[i] = cc_[i];
	}
	sort(sa, 0, n_);
	compress();
	for (m = 1; m < n_; m <<= 1) {
		extend(m);
		sort_(aa1, sa, pp);
		sort_(aa0, pp, sa);
		compress();
	}
	for (i = 0, p = 0; i < n_; i++, p--) {
		a = aa0[i];
		if (a + 1 < n_) {
			j = sa[a + 1], p = max(p, 0);
			while (i + p < n_ && cc_[i + p] == cc_[j + p])
				p++;
			pp[a] = p;
		}
	}
	for (a = 0; a < n_; a++)
		st[n_ + a] = pp[a];
	for (i = n_ - 1; i > 0; i--)
		st[i] = min(st[i << 1 | 0], st[i << 1 | 1]);
}

int lcp(int i, int j) {
	int l, r, tmp, p;

	if (i < 0 || i >= n_ || j < 0 || j >= n_)
		return 0;
	l = aa0[i], r = aa0[j];
	if (l > r)
		tmp = l, l = r, r = tmp;
	if (l == r)
		return n_ - sa[l];
	r--;
	p = n_;
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			p = min(p, st[l++]);
		if ((r & 1) == 0)
			p = min(p, st[r--]);
	}
	return p;
}

int main() {
	static long long kk[N][A], ll[N + 2], mm[N + 2];
	static char cc[N + 1];
	int n, h, i, i_, j_, ij, a;
	long long k_;

	scanf("%s", cc), n = strlen(cc), n_ = n * 2 + 1;
	for (i = 0; i < n; i++)
		cc_[i] = cc_[n + n - i] = cc[i];
	cc_[n] = ' ';
	build();
	for (ij = 0; ij <= n - 1 + n - 1; ij++) {
		int p;

		h = ij / 2, p = lcp(n + n - h, ij - h), i_ = h - p, j_ = ij - i_;
		if (ij % 2 == 0) {
			ll[h] += h - i_, ll[h + 1] -= (h - i_) * 2, ll[h + 2] += h - i_;
			mm[h] -= h - i_, mm[h + 1] += (h - i_) * 2, mm[h + 2] -= h - i_;
		}
		ll[0] += h - i_, ll[1] -= h - i_;
		ll[i_ + 1]--, ll[h + 1]++, ll[ij - h + 1]++, ll[j_ + 1]--;
		mm[i_ + 1]++, mm[h + 1]--, mm[ij - h + 1]--, mm[j_ + 1]++;
		if (i_ < 0 || j_ >= n)
			continue;
		p = lcp(n + n - i_ + 1, j_ + 1) + 1;
		kk[i_][cc[j_] - 'a'] += p, kk[j_][cc[i_] - 'a'] += p;
	}
	for (i = 1; i < n; i++)
		ll[i] += ll[i - 1];
	for (i = 1; i < n; i++)
		ll[i] += ll[i - 1];
	for (i = 1; i < n; i++)
		mm[i] += mm[i - 1];
	for (i = 1; i < n; i++)
		mm[i] += mm[i - 1];
	k_ = 0;
	for (i = 0; i < n; i++)
		for (a = 0; a < A; a++)
			k_ = max(k_, kk[i][a] + ll[i] + (cc[i] == a + 'a' ? mm[i] : 0));
	printf("%lld\n", k_);
	return 0;
}

Compilation message

palinilap.c: In function 'main':
palinilap.c:126:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |  scanf("%s", cc), n = strlen(cc), n_ = n * 2 + 1;
      |  ^~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct

Subtask #2
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1612 KB Output is correct
2 Correct 6 ms 1644 KB Output is correct
3 Correct 7 ms 1680 KB Output is correct
4 Correct 5 ms 1100 KB Output is correct
5 Correct 6 ms 1484 KB Output is correct
6 Correct 8 ms 1704 KB Output is correct
7 Correct 8 ms 1612 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 256 ms 27948 KB Output is correct
2 Correct 154 ms 27944 KB Output is correct
3 Correct 146 ms 27896 KB Output is correct
4 Correct 251 ms 27824 KB Output is correct
5 Correct 264 ms 27900 KB Output is correct
6 Correct 247 ms 27848 KB Output is correct
7 Correct 249 ms 27844 KB Output is correct
8 Correct 132 ms 7620 KB Output is correct
9 Correct 259 ms 27896 KB Output is correct
10 Correct 271 ms 27908 KB Output is correct
11 Correct 157 ms 27832 KB Output is correct
12 Correct 175 ms 27908 KB Output is correct
13 Correct 164 ms 27896 KB Output is correct
14 Correct 229 ms 27908 KB Output is correct
15 Correct 235 ms 27924 KB Output is correct
16 Correct 149 ms 27844 KB Output is correct
17 Correct 330 ms 27996 KB Output is correct
18 Correct 248 ms 28008 KB Output is correct
19 Correct 290 ms 27992 KB Output is correct