Advertisement
seroperson

E / Solution

May 2nd, 2014
261
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.17 KB | None | 0 0
  1. import java.util.Arrays;
  2. import java.util.List;
  3. import java.util.ArrayList;
  4. import java.io.BufferedReader;
  5. import java.io.InputStreamReader;
  6.  
  7. class E {
  8.  
  9.         private static class Rotator {
  10.  
  11.                 private final int[] toRotate, standart;
  12.                 private final List<Integer> history = new ArrayList<Integer>();
  13.  
  14.                 public Rotator(int[] toRotate, int[] standart, int limit) {
  15.                         this.toRotate = toRotate;
  16.                         this.standart = standart;
  17.                 }
  18.  
  19.                 private void rotate(int n, int[] array) {
  20.                         if(n == 0) return;
  21.                         for(int i = 0; i < n/2+1; i++) {
  22.                                 int temp = array[n-i];
  23.                                 array[n-i] = array[i];
  24.                                 array[i] = temp;
  25.                         }
  26.                         history.add(n);
  27.                 }
  28.  
  29.                 private int getElementIndex(int element, int[] array) {
  30.                         for(int elementIndex = 0; elementIndex < array.length; elementIndex++) {
  31.                                 if(array[elementIndex] == element) return elementIndex;
  32.                         }
  33.                         return -1;
  34.                 }
  35.  
  36.                 private void moveElementToBegin(int index, int[] array) {
  37.                         rotate(index, array);
  38.                 }
  39.  
  40.                 private void moveElementToPosition(int index, int position, int[] array) {
  41.                         moveElementToBegin(index, array);
  42.                         rotate(position, array);
  43.                 }
  44.  
  45.                 private int getSortingCandidateIndex(int max, int[] array) {
  46.                         int candidate = Integer.MIN_VALUE;
  47.                         int candidateIndex = 0;
  48.                         for(int index = 0; index < array.length; index++) {
  49.                                 int current = array[index];
  50.                                 if(array[index] > candidate && array[index] < max) {
  51.                                         candidate = current;
  52.                                         candidateIndex = index;
  53.                                 }
  54.                         }
  55.                         return candidateIndex;
  56.                 }
  57.  
  58.                 public List<Integer> sort() {
  59.                         int unSortedMaxIndex = 0;
  60.                         int lastUnSortedIndex = standart.length-1;
  61.                         while(!isFinished()) {
  62.                                 unSortedMaxIndex = getElementIndex(standart[lastUnSortedIndex], toRotate);
  63.                                 if(unSortedMaxIndex != lastUnSortedIndex)
  64.                                         moveElementToPosition(unSortedMaxIndex, lastUnSortedIndex, toRotate);
  65.                                 lastUnSortedIndex--;
  66.                         }
  67.                         return history;
  68.                 }
  69.  
  70.                 public boolean isFinished() {
  71.                         return Arrays.equals(toRotate, standart);
  72.                 }
  73.  
  74.         }
  75.  
  76.         public static void main(String... args) throws Throwable {
  77.  
  78.                 final BufferedReader scanner = new BufferedReader(new InputStreamReader(System.in));
  79.                 int size = Integer.valueOf(scanner.readLine());
  80.                 int[] toSort = new int[size];
  81.                 String[] splitted = scanner.readLine().split(" ");
  82.                 int index = 0;
  83.                 for(String value : splitted) toSort[index++] = Integer.valueOf(value);
  84.                 int[] sorted = Arrays.copyOf(toSort, size);
  85.                 Arrays.sort(sorted);
  86.  
  87.                 Rotator rotator = new Rotator(toSort, sorted, 0);
  88.                 List<Integer> result = rotator.sort();
  89.                 int finalSize = result.size();
  90.                 System.out.println(finalSize);
  91.                 StringBuilder builder = new StringBuilder();
  92.                 String space = " ";
  93.                 for(index = 0; index < finalSize; index++)
  94.                         builder.append(result.get(index)+1).append(space);
  95.                 System.out.print(builder.toString().trim());
  96.  
  97.                 scanner.close();
  98.  
  99.         }
  100.  
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement