#include <stdio.h> #define Max 3000 int positions[Max+1]; int scaled[Max+1]; int reversed[Max+1]; bool visited[Max+1]; int n; int outputCount[Max+1]; int output[Max+1][Max+1]; int lineIdx = 0; int swapIdx = 0; void push(int idx1, int idx2){ output[lineIdx][swapIdx] = idx1; swapIdx++; output[lineIdx][swapIdx] = idx2; swapIdx++; visited[idx1] = true; visited[idx2] = true; //sort int temp = scaled[idx1]; scaled[idx1] = scaled[idx2]; scaled[idx2] = temp; } void swap() { while(1) { bool sorted = true; for(int i=1; i<=n; i++) if(i != scaled[i]) sorted = false; if(sorted) break; lineIdx++; //reset swapIdx = 0; for(int i=1; i<=n; i++) visited[i] = false; for(int i=1; i<=n; i++) reversed[scaled[i]] = i; //pick for(int i=1; i<=n; i++) { int idx1 = i; int idx2 = scaled[idx1]; if(idx1 == idx2) continue; if(idx1 == scaled[idx2]) {//full swap if(visited[idx1] == false && visited[idx2] == false) push(idx1, idx2); } else { //try prepare idx1 int idx3 = scaled[idx2]; if(visited[idx1] == false && visited[idx3] == false) { push(idx1, idx3); visited[idx2] = true; } else { //try prepare idx2 idx3 = reversed[idx1]; if(visited[idx2] == false && visited[idx3] == false) { push(idx2, idx3); visited[idx1] = true; } else { //swap directly if(visited[idx1] == false && visited[idx2] == false) push(idx1, idx2); } } } } outputCount[lineIdx] = swapIdx; } } int main() { scanf("%d", &n); for(int i=1; i <= n; i++) { int a; scanf("%d ", &a); positions[a] = i; } //scale for(int i=1, sIdx=1; i<=Max; i++) { int pos = positions[i]; if(pos > 0) { scaled[pos] = sIdx; sIdx++; } } swap(); //print printf("%d\n", lineIdx); for(int l=1; l<=lineIdx; l++) { int count = outputCount[l]; printf("%d\n", count); for(int s=0; s<count; s+=2) { printf("%d ", output[l][s]); } for(int s=count-1; s>=0; s-=2) { printf("%d ", output[l][s]); } printf("\n"); } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | #include <stdio.h> #define Max 3000 int positions[Max+1]; int scaled[Max+1]; int reversed[Max+1]; bool visited[Max+1]; int n; int outputCount[Max+1]; int output[Max+1][Max+1]; int lineIdx = 0; int swapIdx = 0; void push(int idx1, int idx2){ output[lineIdx][swapIdx] = idx1; swapIdx++; output[lineIdx][swapIdx] = idx2; swapIdx++; visited[idx1] = true; visited[idx2] = true; //sort int temp = scaled[idx1]; scaled[idx1] = scaled[idx2]; scaled[idx2] = temp; } void swap() { while(1) { bool sorted = true; for(int i=1; i<=n; i++) if(i != scaled[i]) sorted = false; if(sorted) break; lineIdx++; //reset swapIdx = 0; for(int i=1; i<=n; i++) visited[i] = false; for(int i=1; i<=n; i++) reversed[scaled[i]] = i; //pick for(int i=1; i<=n; i++) { int idx1 = i; int idx2 = scaled[idx1]; if(idx1 == idx2) continue; if(idx1 == scaled[idx2]) {//full swap if(visited[idx1] == false && visited[idx2] == false) push(idx1, idx2); } else { //try prepare idx1 int idx3 = scaled[idx2]; if(visited[idx1] == false && visited[idx3] == false) { push(idx1, idx3); visited[idx2] = true; } else { //try prepare idx2 idx3 = reversed[idx1]; if(visited[idx2] == false && visited[idx3] == false) { push(idx2, idx3); visited[idx1] = true; } else { //swap directly if(visited[idx1] == false && visited[idx2] == false) push(idx1, idx2); } } } } outputCount[lineIdx] = swapIdx; } } int main() { scanf("%d", &n); for(int i=1; i <= n; i++) { int a; scanf("%d ", &a); positions[a] = i; } //scale for(int i=1, sIdx=1; i<=Max; i++) { int pos = positions[i]; if(pos > 0) { scaled[pos] = sIdx; sIdx++; } } swap(); //print printf("%d\n", lineIdx); for(int l=1; l<=lineIdx; l++) { int count = outputCount[l]; printf("%d\n", count); for(int s=0; s<count; s+=2) { printf("%d ", output[l][s]); } for(int s=count-1; s>=0; s-=2) { printf("%d ", output[l][s]); } printf("\n"); } return 0; } |