#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;
const int N = 1005, L = 1024;
int n, a[N], dt[N], prv[N], inv[N];
bool stb[N];
vector<int> cpr;
vector<pii> ans;
struct segtree {
int v[L];
void init () {
for(int i=0;i<2*L;i++) {
v[i] = 0;
}
}
void upd (int P, int V) {
P += L;
while(P) {
v[P] += V;
P /= 2;
}
}
int get (int S, int E) {
S += L;
E += L;
int R = 0;
while(S <= E) {
if(S%2 == 1) R += v[S++];
if(E%2 == 0) R += v[E--];
S /= 2;
E /= 2;
}
return R;
}
} seg;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
cpr.push_back(a[i]);
}
sort(cpr.begin(), cpr.end());
for(int i=1;i<=n;i++) {
a[i] = n - (lower_bound(cpr.begin(), cpr.end(), a[i]) - cpr.begin());
seg.upd(a[i], 1);
inv[i] = seg.get(a[i]+1, n);
}
seg.init();
for(int i=n;i>=1;i--) {
seg.upd(a[i], 1);
inv[i] += seg.get(1, a[i]-1);
}
int X = 0;
for(int i=1;i<=n;i++) {
int P = i + a[i] - inv[i];
for(int j=0;j<i;j++) {
if(a[i] < a[j] || dt[i] > dt[j] + P) continue;
dt[i] = dt[j] + P;
prv[i] = j;
}
if(dt[X] < dt[i]) X = i;
}
for(int i=X;i;i=prv[i]) {
stb[i] = true;
}
for(int i=1;i<=n;) {
if(stb[i]) {
i++;
continue;
}
int j;
for(j=i+1;j<=n;j++) {
if(stb[j] && a[j] > a[j-1]) break;
swap(a[j], a[j-1]);
swap(stb[j], stb[j-1]);
}
ans.push_back({i, j-1});
stb[j-1] = true;
}
printf("%d\n",(int)ans.size());
for(auto &T : ans) {
printf("%d %d\n",T.X,T.Y);
}
}
Compilation message
sorting.cpp: In function 'int main()':
sorting.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
sorting.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
~~~~~^~~~~~~~~~~~
sorting.cpp:19:9: warning: iteration 1024 invokes undefined behavior [-Waggressive-loop-optimizations]
v[i] = 0;
~~~~~^~~
sorting.cpp:18:16: note: within this loop
for(int i=0;i<2*L;i++) {
~^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
3 ms |
600 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
3 ms |
612 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
4 ms |
864 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
3 ms |
864 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
3 ms |
864 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
4 ms |
864 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
4 ms |
908 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
4 ms |
908 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
6 ms |
952 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
