Submission #544447

#	Time	Username	Problem	Language	Result	Execution time	Memory
544447		rainboy	Ranklist Sorting (BOI07_sorting)	C11	100 / 100	5 ms	4180 KiB

sorting

/* upsolve using booklet */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	1000
#define INF	0x3f3f3f3f

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

int aa[N + 1];

int compare(const void *a, const void *b) {
	int i = *(int *) a;
	int j = *(int *) b;

	return aa[j] - aa[i];
}

int main() {
	static int ii[N + 1], dp[N + 1][N + 1], jj[N + 1];
	static char move[N];
	int n, i, i_, j, a, k;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]);
		ii[i] = i;
	}
	qsort(ii, n, sizeof *ii, compare);
	for (i = 0; i < n; i++)
		aa[ii[i]] = i;
	aa[ii[n] = n] = n;
	memset(dp[n], 0x3f, (n + 1) * sizeof *dp[n]), dp[n][n] = 0;
	for (a = n - 1; a >= 0; a--) {
		int c, x_, j_;

		i_ = 0;
		for (i = 0; i < ii[a]; i++)
			if (aa[i] < a)
				i_++;
		for (i = 0, j = 0; i <= n; i++) {
			if (aa[i] < a)
				j++;
			dp[a][i] = min(dp[a + 1][i] + (i_ + 1) + (j + 1), INF);
		}
		c = 0, x_ = INF, j_ = -1;
		for (j = ii[a] + 1; j <= n; j++) {
			int x = dp[a + 1][j] + c;

			if (x_ > x)
				x_ = x, j_ = j;
			c += max(a - aa[j], 0);
		}
		dp[a][ii[a]] = x_, jj[a] = j_;
	}
	i_ = -1;
	for (i = 0; i <= n; i++)
		if (i_ == -1 || dp[0][i_] > dp[0][i])
			i_ = i;
	k = 0;
	for (a = 0, i = i_; a < n; a++)
		if (i != ii[a])
			move[a] = 1, k++;
		else
			i = jj[a];
	printf("%d\n", k);
	for (a = n - 1; a >= 0; a--)
		if (move[a]) {
			i = 0;
			while (aa[i] != a)
				i++;
			j = 0;
			while (aa[j] != a + 1)
				j++;
			if (i < j) {
				printf("%d %d\n", i + 1, j);
				while (i + 1 < j)
					aa[i] = aa[i + 1], i++;
				aa[i] = a;
			} else {
				printf("%d %d\n", i + 1, j + 1);
				while (i > j)
					aa[i] = aa[i - 1], i--;
				aa[i] = a;
			}
		}
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100