Järjestys

import java.util.*;
 
public class Jarjestys4 {
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        int n = Integer.parseInt(scanner.nextLine());
        String[] stringArray = scanner.nextLine().split(" ");
        int[] array = new int[stringArray.length];
 
        for (int i = 0; i < stringArray.length; i++) {
            array[i] = Integer.parseInt(stringArray[i]);
        }
        /*int[] array = new int[n];
        for (int i = 0; i < array.length; i++) {
            array[i] = i;
        }
        List<Integer> arrayList = new ArrayList<>();
        for (int i : array) {
            arrayList.add(i + 1);
        }
        Collections.shuffle(arrayList, new Random(3));
        for (int i = 0; i < arrayList.size(); i++) {
            array[i] = arrayList.get(i);
        }
 
        double startTime = System.nanoTime();
        double reverseTime = 0;
        double searchTime = 0;*/
 
        int biggestNum = n;
        int nextIndex = 0;
        for (int i = 0; i != array.length; i++) {
            if (array[i] == biggestNum) {
                nextIndex = i;
                break;
            }
        }
 
        int startIndex = 0;
        int stopIndex = array.length - 1;
        List<Integer> reversals = new ArrayList<>(2 * n);
 
        while (startIndex != stopIndex) {
 
            final boolean traverseBackWards = startIndex > stopIndex;
 
            int currentNumberIndex = nextIndex;
 
            if (currentNumberIndex == stopIndex) {
                if (traverseBackWards) {
                    stopIndex++;
                } else {
                    stopIndex--;
                }
                nextIndex = indexOf(array, --biggestNum, startIndex, stopIndex);
                continue;
            }
 
            if (currentNumberIndex != startIndex) {
                if (traverseBackWards) {
                    //double startReverse = System.nanoTime();
                    nextIndex = reverse(array, currentNumberIndex, startIndex, --biggestNum);
                    if (nextIndex == -1) {
                        nextIndex = indexOf(array, biggestNum, stopIndex, currentNumberIndex - 1);
                    }
 
                    //reverseTime += System.nanoTime() - startReverse;
                    reversals.add(startIndex - currentNumberIndex + 1);
                } else {
                    //double startReverse = System.nanoTime();
                    nextIndex = reverse(array, startIndex, currentNumberIndex, --biggestNum);
                    if (nextIndex == -1) {
                        nextIndex = indexOf(array, biggestNum, currentNumberIndex + 1, stopIndex);
                    }
                    //reverseTime += System.nanoTime() - startReverse;
                    reversals.add(currentNumberIndex - startIndex + 1);
                }
            } else {
                nextIndex = indexOf(array, --biggestNum, startIndex, stopIndex);
            }
 
            if (traverseBackWards) {
                reversals.add(startIndex - stopIndex + 1);
 
                final int temp = startIndex;
                startIndex = stopIndex;
                stopIndex = temp - 1;
 
            } else {
                reversals.add(stopIndex - startIndex + 1);
 
                final int temp = startIndex;
                startIndex = stopIndex;
                stopIndex = temp + 1;
 
            }
 
        }
 
        //System.out.println((System.nanoTime() - startTime) / 1000000000d + " seconds");
        //System.out.println((reverseTime) / 1000000000d + " seconds on reversing");
        //System.out.println((searchTime) / 1000000000d + " seconds on searching");
 
        System.out.println(reversals.size());
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < reversals.size(); i++) {
            result.append(reversals.get(i));
            if (i != reversals.size() - 1) {
                result.append(" ");
            }
        }
        System.out.println(result.toString());
    }
 
    private static int indexOf(int[] array, int num, int start, int stop) {
        if (start > stop) {
            int temp = start;
            start = stop;
            stop = temp;
        }
        stop++;
        for (int i = start; i != stop; i++) {
            if (array[i] == num) {
                return i;
            }
        }
        return -1;
    }
 
    private static int reverse(int[] array, int startIndex, int stopIndex, int numToSearch) {
        int numIndex = -1;
        while (startIndex < stopIndex) {
          
            final int temp = array[startIndex];
            array[startIndex] = array[stopIndex];
            array[stopIndex] = temp;
            if (temp == numToSearch) {
                numIndex = stopIndex;
            } else if (array[startIndex] == numToSearch) {
                numIndex = startIndex;
            }
 
            startIndex++;
            stopIndex--;
        }
 
        if (startIndex == stopIndex && array[startIndex] == numToSearch) {
            return startIndex;
        }
 
        return numIndex;
    }
 
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED