제출 #486546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
486546		rainboy	Palinilap (COI16_palinilap)	C11	100 / 100	330 ms	28008 KiB

palinilap

#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;
}

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

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 / 17
• Subtask 2: 37 / 37
• Subtask 3: 46 / 46