CSES - Datatähti 2017 alku - Results
Submission details
Task:Järjestys
Sender:JesseNiininen
Submission time:2016-10-11 21:36:49 +0300
Language:Java
Status:READY
Result:56
Feedback
groupverdictscore
#1ACCEPTED19
#2ACCEPTED37
#30
Test results
testverdicttimegroup
#1ACCEPTED0.12 s1details
#2ACCEPTED0.20 s2details
#3--3details

Code

import java.util.*;

public class Jarjestys6 {

    private static int[] array;
    private static List<Integer> reversals;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = Integer.parseInt(scanner.nextLine());
        String[] stringArray = scanner.nextLine().split(" ");
        array = new int[stringArray.length];

        for (int i = 0; i < stringArray.length; i++) {
            array[i] = Integer.parseInt(stringArray[i]);
        }
        /*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;

        reversals = new ArrayList<>(2 * n);

        order(0, n - 1, n);

        //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 order(int startIndex, int stopIndex, int currentNum) {

        if (startIndex == stopIndex || currentNum < 1) {
            return 0;
        }

        int currentNumIndex = -1;
        for (int i = startIndex; i <= stopIndex; i++) {
            if (array[i] == currentNum) {
                currentNumIndex = i;
                break;
            }
        }

        if (currentNumIndex == -1) {
            return 0;
        }

        int numsInOrder = 1;
        if (currentNumIndex == stopIndex) {
            numsInOrder += order(startIndex, stopIndex - 1, currentNum - 1);
            return numsInOrder;
        }

        if (currentNumIndex != startIndex) {
            numsInOrder += order(startIndex, currentNumIndex - 1, currentNum - 1);
            reverse(startIndex, currentNumIndex);
            reversals.add(currentNumIndex - startIndex + 1);
        }

        reverse(startIndex, stopIndex);
        reversals.add(stopIndex + 1);
        return numsInOrder + order(startIndex, stopIndex - 1, currentNum - 1);
        /*final int temp = startIndex;
            startIndex = stopIndex;
            stopIndex = temp + 1;*/

    }

    private static void reverse(int startIndex, int stopIndex) {
        while (startIndex < stopIndex) {
            final int temp = array[startIndex];
            array[startIndex] = array[stopIndex];;
            array[stopIndex] = temp;
            startIndex++;
            stopIndex--;
        }
    }

}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
10
9 3 4 7 6 5 10 2 8 1

correct output
32
10 10 9 10 9 8 7 9 4 2 1 4 5 2...

user output
11
6 7 10 2 8 3 7 4 6 4 2

Test 2

Group: 2

Verdict: ACCEPTED

input
1000
650 716 982 41 133 1000 876 92...

correct output
3984
207 207 206 207 128 127 126 12...

user output
1964
6 1000 204 868 27 867 869 903 ...

Test 3

Group: 3

Verdict:

input
100000
94703 47808 62366 31885 7091 8...

correct output
399956
98676 98676 98675 98676 62994 ...

user output
(empty)