CSES - Datatähti 2017 alku - Results
Submission details
Task:Järjestys
Sender:planckcons
Submission time:2016-10-05 21:29:37 +0300
Language:Java
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.14 s1details
#20.89 s2details
#3--3details

Code

import java.util.Scanner;
import static java.lang.System.arraycopy;
import java.util.Arrays;
import java.util.Collections;

public class Jarjestys {

    static int[] arr;
    static int n;
    static int c;    

    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        
        arr = new int[n];
        
        for(int i = 0; i < n; i++)
        {
            arr[i] = scan.nextInt();
        }
        
        String fin = "";
        for(int i = n; i > 0; i--)
        {
            fin += finder(i);
            for(int j = 0; j < i; j++)
                System.out.print(arr[j]);
            System.out.println();
            
        }
	System.out.println(c + " " + fin);
    }
    
    public static int[] swapA(int n2, int[] arr, int p)
    {
        int a = n2-(p+1); 
        int[] arr2 = new int[n2];
        int[] arr3 = new int[a];
        arraycopy(arr, 0, arr2, a, p+1);
        arraycopy(arr, p+1, arr3, 0, a);
        reverse(arr3, 0, a);
        arraycopy(arr3, 0, arr2, 0, a);
        return arr2;
    }
    
    public static int[] swapB(int n2, int[] arr)
    {
        int[] arr2 = new int[n2];
        reverse(arr, 0, n2);
        arraycopy(arr, 0, arr2, 0, n2);
        return arr2;
    }   
    
    public static int[] swapC(int n2, int[] arr)
    {
        int[] arr2 = new int[n2];
        arraycopy(arr, 0, arr2, 0, n2);
        return arr2;
    }
       
    static String finder(int i)
    {
        if(arr[i-1] == i)
        {
            arr = swapC(i, arr);
            return "";
        }
        if(arr[0] == i)
        {
            arr = swapB(i, arr);
            c++;
            return i + " ";
        }       
        for(int j = 1; j < i-1; j++)
        {
            if(arr[j] == i)
            {
                arr = swapA(i ,arr, j);
                c += 2;
                return j+1 + " " + i + " ";
            }       
        }
        
        return "";
    }
    
    public static void reverse(final int[] array, final int startIndexInclusive, final int endIndexExclusive) {
        if (array == null) {
            return;
        }
        int i = startIndexInclusive < 0 ? 0 : startIndexInclusive;
        int j = Math.min(array.length, endIndexExclusive) - 1;
        int tmp;
        while (j > i) {
            tmp = array[j];
            array[j] = array[i];
            array[i] = tmp;
            j--;
            i++;
        }
    }    
}

Test details

Test 1

Group: 1

Verdict:

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
18293476510
567431829
25674318
1342567
134256
...

Test 2

Group: 2

Verdict:

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

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

user output
905829667956494644262286677288...

Test 3

Group: 3

Verdict:

input
100000
94703 47808 62366 31885 7091 8...

correct output
399956
98676 98676 98675 98676 62994 ...

user output
(empty)