Submission #544446

#	Time	Username	Problem	Language	Result	Execution time	Memory
544446		rainboy	RLE (BOI06_rle)	C11	100 / 100	504 ms	56328 KiB

rle

#include <stdio.h>

#define N	2000000
#define M	100000

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

int iq[1 + M], pq[M], cnt, dp[M];

int lt(int i, int j) { return dp[i] < dp[j]; }

int p2(int p) {
	return (p *= 2) > cnt ? 0 : p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p;
}

void pq_up(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

int pq_first() {
	return iq[1];
}

int main() {
	static int hh[N], hh_[N];
	static long long kk[N];
	int n, n_, m, h, i, sum;

	scanf("%d%d", &m, &n);
	for (i = 0; i < n; i++)
		scanf("%d", &hh[i]);
	n_ = 0;
	for (h = 0, i = 0; i < n; i++)
		if (hh[i] != h)
			hh[n_] = hh[i], kk[n_] = 1, n_++;
		else {
			if (hh[i + 1] == h)
				hh[n_] = h, kk[n_] = hh[i + 2] + 1, n_++;
			else if (hh[i + 2] == 0)
				h = hh[i + 1];
			else
				hh[n_] = hh[i + 1], kk[n_] = hh[i + 2] + 3, n_++;
			i += 2;
		}
	n = n_, n_ = 0;
	for (i = 0; i < n; i++)
		if (n_ == 0 || hh[n_ - 1] != hh[i])
			hh[n_] = hh[i], kk[n_] = kk[i], n_++;
		else
			kk[n_ - 1] += kk[i];
	n = n_;
	for (h = 0; h < m; h++)
		iq[pq[h] = ++cnt] = h;
	sum = 0;
	for (i = n - 1; i >= 0; i--) {
		int k, k_, h, h_;

		k = kk[i] / (m + 2) * 3 + min(kk[i] % (m + 2), 3), k_ = (kk[i] + m - 1) / m * 3;
		sum += k;
		h = hh[i];
		dp[h] += k_ - k, pq_dn(h);
		h_ = pq_first();
		if (dp[h] > dp[h_] + 3) {
			hh_[i] = h_;
			dp[h] = dp[h_] + 3, pq_up(h);
		} else
			hh_[i] = -1;
	}
	printf("%d\n", sum + dp[0]);
	for (h = 0, i = 0; i < n; i++) {
		if (hh[i] == h && hh_[i] != -1)
			printf("%d %d 0 ", h, hh_[i]), h = hh_[i];
		if (hh[i] != h) {
			while (kk[i] >= m + 2) {
				printf("%d %d %d ", h, hh[i], m - 1);
				kk[i] -= m + 2;
			}
			if (kk[i] <= 3)
				while (kk[i]--)
					printf("%d ", hh[i]);
			else
				printf("%d %d %lld ", h, hh[i], kk[i] - 3);
		} else {
			while (kk[i] >= m) {
				printf("%d %d %d ", h, h, m - 1);
				kk[i] -= m;
			}
			if (kk[i] > 0)
				printf("%d %d %lld ", h, h, kk[i] - 1);
		}
	}
	printf("\n");
	return 0;
}

Compilation message (stderr)

rle.c: In function 'main':
rle.c:41:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d%d", &m, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~
rle.c:43:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d", &hh[i]);
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100