Task: | Järjestys |
Sender: | JesseNiininen |
Submission time: | 2016-10-11 21:36:49 +0300 |
Language: | Java |
Status: | READY |
Result: | 56 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 19 |
#2 | ACCEPTED | 37 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.12 s | 1 | details |
#2 | ACCEPTED | 0.20 s | 2 | details |
#3 | TIME LIMIT EXCEEDED | -- | 3 | details |
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: TIME LIMIT EXCEEDED
input |
---|
100000 94703 47808 62366 31885 7091 8... |
correct output |
---|
399956 98676 98676 98675 98676 62994 ... |
user output |
---|
(empty) |