Task: | Järjestys |
Sender: | JesseNiininen |
Submission time: | 2016-10-15 17:29:04 +0300 |
Language: | Java |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 19 |
#2 | ACCEPTED | 37 |
#3 | ACCEPTED | 44 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.14 s | 1 | details |
#2 | ACCEPTED | 0.17 s | 2 | details |
#3 | ACCEPTED | 1.31 s | 3 | details |
Code
import java.util.*;public class Jarjestys7 {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]);}List<Integer> reversals = insertionSort(array);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 List<Integer> insertionSort(int[] array) {List<Integer> reversals = new ArrayList<>();for (int i = 1; i < array.length; i++) {int index = getIndex(array, i - 1, array[i]);if (index == i) {continue;}int temp = array[i];System.arraycopy(array, index, array, index + 1, i - index);array[index] = temp;if (index - 1 > 0) {reversals.add(index);}if (i - 1 > 0) {reversals.add(i);}reversals.add(i + 1);if (index > 0) {reversals.add(index + 1);}}return reversals;}private static int getIndex(int[] array, int high, int num) {int low = 0;if (num < array[0]) {return 0;}if (num > array[high]) {return high + 1;}while (true) {int middle = (low + high) / 2;if (array[middle] < num) {if (array[middle + 1] >= num) {return middle + 1;}low = middle + 1;} else {if (array[middle - 1] <= num) {return middle;}high = middle - 1;}}}}
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 |
---|
24 2 2 3 2 2 3 4 3 2 4 5 3 2 5 6 ... |
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 |
---|
3973 3 4 4 5 2 4 6 7 5 7 8 2 7 8 9 ... |
Test 3
Group: 3
Verdict: ACCEPTED
input |
---|
100000 94703 47808 62366 31885 7091 8... |
correct output |
---|
399956 98676 98676 98675 98676 62994 ... |
user output |
---|
399912 2 2 3 2 3 4 4 5 4 5 6 5 4 6 7 ... |