Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Arrays;
- import java.util.List;
- import java.util.ArrayList;
- import java.io.BufferedReader;
- import java.io.InputStreamReader;
- class E {
- private static class Rotator {
- private final int[] toRotate, standart;
- private final List<Integer> history = new ArrayList<Integer>();
- public Rotator(int[] toRotate, int[] standart, int limit) {
- this.toRotate = toRotate;
- this.standart = standart;
- }
- private void rotate(int n, int[] array) {
- if(n == 0) return;
- for(int i = 0; i < n/2+1; i++) {
- int temp = array[n-i];
- array[n-i] = array[i];
- array[i] = temp;
- }
- history.add(n);
- }
- private int getElementIndex(int element, int[] array) {
- for(int elementIndex = 0; elementIndex < array.length; elementIndex++) {
- if(array[elementIndex] == element) return elementIndex;
- }
- return -1;
- }
- private void moveElementToBegin(int index, int[] array) {
- rotate(index, array);
- }
- private void moveElementToPosition(int index, int position, int[] array) {
- moveElementToBegin(index, array);
- rotate(position, array);
- }
- private int getSortingCandidateIndex(int max, int[] array) {
- int candidate = Integer.MIN_VALUE;
- int candidateIndex = 0;
- for(int index = 0; index < array.length; index++) {
- int current = array[index];
- if(array[index] > candidate && array[index] < max) {
- candidate = current;
- candidateIndex = index;
- }
- }
- return candidateIndex;
- }
- public List<Integer> sort() {
- int unSortedMaxIndex = 0;
- int lastUnSortedIndex = standart.length-1;
- while(!isFinished()) {
- unSortedMaxIndex = getElementIndex(standart[lastUnSortedIndex], toRotate);
- if(unSortedMaxIndex != lastUnSortedIndex)
- moveElementToPosition(unSortedMaxIndex, lastUnSortedIndex, toRotate);
- lastUnSortedIndex--;
- }
- return history;
- }
- public boolean isFinished() {
- return Arrays.equals(toRotate, standart);
- }
- }
- public static void main(String... args) throws Throwable {
- final BufferedReader scanner = new BufferedReader(new InputStreamReader(System.in));
- int size = Integer.valueOf(scanner.readLine());
- int[] toSort = new int[size];
- String[] splitted = scanner.readLine().split(" ");
- int index = 0;
- for(String value : splitted) toSort[index++] = Integer.valueOf(value);
- int[] sorted = Arrays.copyOf(toSort, size);
- Arrays.sort(sorted);
- Rotator rotator = new Rotator(toSort, sorted, 0);
- List<Integer> result = rotator.sort();
- int finalSize = result.size();
- System.out.println(finalSize);
- StringBuilder builder = new StringBuilder();
- String space = " ";
- for(index = 0; index < finalSize; index++)
- builder.append(result.get(index)+1).append(space);
- System.out.print(builder.toString().trim());
- scanner.close();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement