-
Notifications
You must be signed in to change notification settings - Fork 2
/
Solution.java
58 lines (49 loc) · 1.27 KB
/
Solution.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package com.algorithm.playground.google.codejam._2018.qualification.task2;
import java.util.Arrays;
import java.util.Scanner;
/**
* https://codingcompetitions.withgoogle.com/codejam/round/00000000000000cb/00000000000079cb
*/
public class Solution {
public static void main(String[] args) {
try (Scanner console = new Scanner(System.in)) {
int tests = console.nextInt();
for (int test = 1; test <= tests; test++) {
int[] nums = new int[console.nextInt()];
for (int i = 0; i < nums.length; i++) {
nums[i] = console.nextInt();
}
int ans = solve(nums);
System.out.println(String.format("Case #%s: %s", test, ans == -1 ? "OK" : ans));
}
} catch (Exception e) {
e.printStackTrace(System.out);
}
}
static int solve(int[] nums) {
int[] odd = new int[nums.length >> 1];
int[] even = new int[nums.length - odd.length];
for (int i = 0; i < nums.length; i++) {
int idx = i >> 1;
if (i % 2 == 0) {
even[idx] = nums[i];
} else {
odd[idx] = nums[i];
}
}
Arrays.sort(odd);
Arrays.sort(even);
for (int i = 0; i < nums.length; i++) {
int idx = i >> 1;
if (i % 2 == 0) {
nums[i] = even[idx];
} else {
nums[i] = odd[idx];
}
if (i != 0 && nums[i - 1] > nums[i]) {
return i - 1;
}
}
return -1;
}
}