#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef pair<int, int> pi;
const int MM = 1005, INF=0x3f3f3f3f;
int N, p[MM], cnt[MM][MM], ans=INF, dp[MM][MM], st, dep[MM], tot, bit[MM]; pi a[MM];
bool cmp(pi x, pi y){ return x.s < y.s;}
void upd(int pos, int val){
for(int i=pos; i<=N; i+=i&-i)
bit[i] += val;
}
int qry(int pos) {
int ret = 0;
for(int i=pos; i; i-=i&-i) ret += bit[i];
return ret;
}
void recur(int cur, int best) {
if(cur == N+1) return;
if(p[cur] == best) recur(cur+1, dep[cur]);
else { a[tot++] = {p[cur], cur}; recur(cur+1, best); }
}
int main(){
//freopen("test.txt", "r", stdin);
scanf("%d", &N);
for(int i=1; i<=N; i++){
scanf("%d", &a[i].f); a[i].s = i;
}
sort(a+1, a+N+1, greater<pi>());
for(int i=1; i<=N; i++) {
p[i] = a[i].s; a[i].f = i;
}
sort(a+1, a+N+1, cmp);
for(int i=1; i<=N; i++)
cnt[a[i].f+1][i+1]++;
for(int i=1; i<=N+1; i++)
for(int j=1; j<=N+1; j++)
cnt[i][j] += cnt[i][j-1] + cnt[i-1][j] - cnt[i-1][j-1];
memset(dp, 0x3f, sizeof(dp));
a[N+1].f = N+1; dp[N+1][N+1] = 0;
for(int i=N; i>=1; i--){
for(int j=1; j<=N+1; j++)
if(dp[i+1][j] != INF) dp[i][j] = dp[i+1][j] + cnt[i][p[i]] + cnt[i][j] + 2;
for(int j=p[i]+1, val=0; j<=N+1; j++){
if(dp[i][p[i]] >= dp[i+1][j] + val){
dp[i][p[i]]= dp[i+1][j]+val;
dep[i] = j;
}
if(a[j].f < i) val = val + i - a[j].f;
}
}
// for(int i=1; i<=N+1; i++){
// for(int j=1; j<=N+1; j++){
// if(dp[i][j] == INF) cout << "INF\t";
// else cout << dp[i][j] << "\t";
// }
// cout << endl;
// }
for(int i=1; i<=N; i++){
if(dp[1][i] <= ans) ans = dp[1][i], st = i;
upd(i, 1);
}
recur(1, st);
printf("%d\n", tot);
for(int i=tot-1; i>=0; i--){
printf("%d %d\n", qry(a[i].first), a[i].second);
upd(a[i].first, -1);
}
}
Compilation message
sorting.cpp: In function 'int main()':
sorting.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
sorting.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i].f); a[i].s = i;
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
4344 KB |
Output is correct |
| 2 |
Correct |
6 ms |
4316 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
4344 KB |
not sorted |
| 4 |
Incorrect |
6 ms |
4472 KB |
not sorted |
| 5 |
Incorrect |
6 ms |
4728 KB |
not sorted |
| 6 |
Incorrect |
8 ms |
5112 KB |
not sorted |
| 7 |
Incorrect |
9 ms |
6264 KB |
not sorted |
| 8 |
Incorrect |
12 ms |
7416 KB |
not sorted |
| 9 |
Correct |
14 ms |
8312 KB |
Output is correct |
| 10 |
Incorrect |
15 ms |
8184 KB |
not sorted |
