#include <bits/stdc++.h>
using namespace std;
int A[11], B[11];
bool chk[11];
vector <int> X;
int n, v, ans;
void move(int a, int b)
{
int i, t;
if(a <= b){
t = B[a];
for(i=a; i<b; i++) B[i] = B[i+1];
B[b] = t;
}
else{
t = B[a];
for(i=a; i>b; i--) B[i] = B[i-1];
B[b] = t;
}
}
int check(int t)
{
int i, j, k, ret = 0;
vector <int> V;
V.push_back(0);
for(i=1; i<=n; i++){
if(t & (1 << i-1)){
V.push_back(A[i]);
chk[A[i]] = 1;
}
else chk[A[i]] = 0;
B[i] = A[i];
}
for(;;){
for(i=1; i<=n; i++) if(!chk[B[i]]) break;
if(i > n) break;
for(k=0; k<V.size(); k++){
if(V[k] >= B[i]) break;
} k --;
for(j=0; j<n; j++) if(B[j] == V[k]) break;
if(i > j) j ++;
V.push_back(B[i]);
chk[B[i]] = 1;
for(k=V.size()-1; k>0; k--){
if(V[k] < V[k-1]) swap(V[k], V[k-1]);
}
ret += i + j;
move(i, j);
}
return ret;
}
void print(int t)
{
int i, j, k, s = 0;
vector <int> V;
V.push_back(0);
for(i=1; i<=n; i++){
if(t & (1 << i-1)){
V.push_back(A[i]);
chk[A[i]] = 1;
}
else chk[A[i]] = 0, s ++;
B[i] = A[i];
}
printf("%d\n", s);
for(;;){
for(i=1; i<=n; i++) if(!chk[B[i]]) break;
if(i > n) break;
for(k=0; k<V.size(); k++){
if(V[k] >= B[i]) break;
} k --;
for(j=0; j<n; j++) if(B[j] == V[k]) break;
if(i > j) j ++;
V.push_back(B[i]);
chk[B[i]] = 1;
for(k=V.size()-1; k>0; k--){
if(V[k] < V[k-1]) swap(V[k], V[k-1]);
}
printf("%d %d\n", i, j);
move(i, j);
}
}
int main()
{
int i, j, p, k;
v = 1e9;
scanf("%d", &n);
for(i=1; i<=n; i++){
scanf("%d", A+i);
X.push_back(A[i]);
}
sort(X.begin(), X.end());
X.erase(unique(X.begin(), X.end()), X.end());
for(i=1; i<=n; i++){
A[i] = X.end() - lower_bound(X.begin(), X.end(), A[i]);
}
for(i=1; i<(1<<n); i++){
p = 0;
for(j=1; j<=n; j++){
if(i & (1 << j-1)){
if(A[p] > A[j]) break;
p = j;
}
}
if(j <= n) continue;
k = check(i);
if(k < v) v = k, ans = i;
}
print(ans);
return 0;
}
Compilation message
sorting.cpp: In function 'int check(int)':
sorting.cpp:33:17: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
if(t & (1 << i-1)){
~^~
sorting.cpp:45:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(k=0; k<V.size(); k++){
~^~~~~~~~~
sorting.cpp: In function 'void print(int)':
sorting.cpp:73:17: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
if(t & (1 << i-1)){
~^~
sorting.cpp:87:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(k=0; k<V.size(); k++){
~^~~~~~~~~
sorting.cpp: In function 'int main()':
sorting.cpp:129:18: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
if(i & (1 << j-1)){
~^~
sorting.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
sorting.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", A+i);
~~~~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
408 KB |
Output is correct |
| 4 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
2 ms |
676 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
13 ms |
688 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
3 ms |
816 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
3 ms |
836 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
2 ms |
984 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
