oj.uz

답안 #544447

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
544447 2022-04-01T23:42:57 Z rainboy Ranklist Sorting (BOI07_sorting) C
100 / 100
 5 ms 4180 KB 
/* 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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 2 ms 2260 KB Output is correct
8 Correct 4 ms 3412 KB Output is correct
9 Correct 4 ms 4180 KB Output is correct
10 Correct 5 ms 4144 KB Output is correct