/* 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]);
| ^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
