Submission #544446

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
544446	2022-04-01T23:42:11 Z	rainboy	RLE (BOI06_rle)	C	100 / 100	504 ms	56328 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	304 KB	Output is correct
5	Correct	1 ms	300 KB	Output is correct
6	Correct	17 ms	1592 KB	Output is correct
7	Correct	136 ms	10884 KB	Output is correct
8	Correct	175 ms	15392 KB	Output is correct
9	Correct	306 ms	27992 KB	Output is correct
10	Correct	137 ms	10752 KB	Output is correct
11	Correct	107 ms	9544 KB	Output is correct
12	Correct	209 ms	19536 KB	Output is correct
13	Correct	284 ms	25736 KB	Output is correct
14	Correct	88 ms	9244 KB	Output is correct
15	Correct	45 ms	4988 KB	Output is correct
16	Correct	302 ms	28508 KB	Output is correct
17	Correct	343 ms	33052 KB	Output is correct
18	Correct	347 ms	34780 KB	Output is correct
19	Correct	504 ms	56328 KB	Output is correct
20	Correct	481 ms	56152 KB	Output is correct