CSES - Datatähti 2017 alku - Results
Submission details
Task:Järjestys
Sender:MM
Submission time:2016-10-08 17:38:08 +0300
Language:Java
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.19 s1details
#20.31 s2details
#31.11 s3details

Code

import java.util.Arrays;
import java.util.Scanner;
import java.util.function.IntBinaryOperator;

public class Jarjestys implements IntBinaryOperator {

	public static void main(String[] args) {
		Scanner reader = new Scanner(System.in);
		int loop = reader.nextInt();
		int[] sortedNumbers = new int[loop];
		int i = 0;
		for (i=0;i<loop;i++) {
			sortedNumbers[i] = reader.nextInt();
		}
		int[] numbers = sortedNumbers.clone();
		Arrays.parallelSort(sortedNumbers);
		//-----------------------------------------
		int[] amounts = new int[1000000];
		
		for (int key : numbers) {
			amounts[key]++;
		}
		Arrays.parallelPrefix(amounts, new Jarjestys());
		
		//-----------------------------------------
		//Replace numbers with indexes
		for (i=0;i<numbers.length;i++) {
			numbers[i] = --amounts[numbers[i]];
		}
		int[] sortOrder = sortArray(numbers);
		int maara = 0;
		for (int num : sortOrder)
			if (num > 0)
				maara++;
		System.out.println(maara);
		for (int num : sortOrder)
			if (num > 0)
				System.out.print((num + 1) + " ");
		System.out.print("\n");
		reader.close();
	}
	
	private static int[] sortArray(int[] array) { //TODO: case 1 1 2 0
		int[] sortedArray = array.clone();
		Arrays.parallelSort(sortedArray);
		int index, i = 0;
		int[] sortOrder = new int[5*array.length];
		while ((sortOrder[i++] = index = checkIfSorted(array, sortedArray)) != -1) {
			sortOrder[i++] = index = swap(array, index);
			while (index != 0) {
				sortOrder[i++] = index = swap(array, index);
			}
		}
		return sortOrder;
	}
	
	private static int checkIfSorted(int[] array, int[] sortedArray) { //FIXME: add support for same indexes
		int i;
		for (i=0;i<array.length-1;i++) {
			if (array[i] != sortedArray[i])
				return i;
		}
		return -1;
	}
	
	private static int swap(int[] array, int index) {
		int newIndex = array[index];
		array[index] = array[0];
		array[0] = newIndex;
		return newIndex;
	}

	@Override
	public int applyAsInt(int left, int right) {
		return left + right;
	}
}

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
10
9 8 2 3 4 7 10 5 6 5 

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
1000
650 328 760 478 737 281 696 98...

Test 3

Group: 3

Verdict:

input
100000
94703 47808 62366 31885 7091 8...

correct output
399956
98676 98676 98675 98676 62994 ...

user output
100008
94703 71577 78918 31721 46072 ...