#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[(sz(V)-2)])
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const bool debug = 0;
const int MAXN = 2005;
vector<pii> Ans;
int A[MAXN], B[MAXN];
int N;
int main() {
ios::sync_with_stdio(false);
cin >> N;
{
vector<int> V;
for(int i = 1; i <= N; i++) {
cin >> A[i];
V.eb(A[i]);
}
sorv(V);
for(int i = 1; i <= N; i++)
A[i] = N - int(lower_bound(allv(V), A[i]) - V.begin());
}
if(debug) {
for(int i = 1; i <= N; i++) printf("%d ", A[i]); puts("");
}
if(N <= 10) {
int ret = INF;
for(int key = 0; key < (1<<N); key++) {
vector<pii> V; int sum = 0;
for(int i = 1; i <= N; i++) B[i] = A[i];
int s = 1, e = N;
for(int t = 0; t < N; t++) {
if(key & (1<<t)) {
int idx = -1;
for(int j = s; j <= e; j++) if(s == B[j]) idx = j;
if(idx == s) { s++; continue; }
V.eb(idx, s); sum += idx+s;
rotate(B+s, B+idx, B+idx+1);
s++;
} else {
int idx = -1;
for(int j = s; j <= e; j++) if(e == B[j]) idx = j;
if(idx == e) { e--; continue; }
V.eb(idx, e); sum += idx+e;
rotate(B+idx, B+idx+1, B+e+1);
e--;
}
}
if(ret <= sum) continue;
ret = sum; swap(Ans, V);
}
ret = 0;
for(int i = 0; i < 10000; i++) for(int j = 0; j < 10000; j++)
ret = (ret + i + j) % 998353244;
if(!ret) puts("WTF?");
} else {
for(int i = N; i; i--) {
int idx = -1;
for(int j = 1; j <= i; j++) if(i == A[j]) idx = j;
if(idx == i) continue;
Ans.eb(idx, i);
rotate(A+idx, A+idx+1, A+i+1);
if(debug) {
for(int j = 1; j <= N; j++) printf("%d ", A[j]); puts("");
}
}
}
printf("%d\n", sz(Ans));
for(auto &p : Ans) printf("%d %d\n", p.first, p.second);
return 0;
}
Compilation message
sorting.cpp: In function 'int main()':
sorting.cpp:47:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(int i = 1; i <= N; i++) printf("%d ", A[i]); puts("");
^~~
sorting.cpp:47:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(int i = 1; i <= N; i++) printf("%d ", A[i]); puts("");
^~~~
sorting.cpp:96:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(int j = 1; j <= N; j++) printf("%d ", A[j]); puts("");
^~~
sorting.cpp:96:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(int j = 1; j <= N; j++) printf("%d ", A[j]); puts("");
^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
558 ms |
468 KB |
Output is correct |
| 2 |
Correct |
547 ms |
488 KB |
Output is correct |
| 3 |
Incorrect |
567 ms |
564 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
564 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
564 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
628 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
628 KB |
Output isn't correct |
| 8 |
Incorrect |
3 ms |
628 KB |
Output isn't correct |
| 9 |
Correct |
3 ms |
628 KB |
Output is correct |
| 10 |
Incorrect |
3 ms |
628 KB |
Output isn't correct |
