Submission #1608211
Source Code Expand
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Main {
private static int solve(int N, int[] nums) {
// decrement nums
for (int i = 0; i < N; i ++) {
nums[i] --;
}
// list up all problematic places
// list up all score
LinkedList<Integer> problematics = new LinkedList<>();
int[] scores = new int[N];
for (int i = 0; i < N; i ++) {
if (i == nums[i]) problematics.add(i);
scores[i] = score(nums, i); // same with nums[i] + score
}
int nSwap = 0;
long nProbs = problematics.stream().count();
while (nProbs != 0) {
int targetInd = problematics.getFirst();
if (targetInd == 0) {
swap(nums, 0, 1);
scores[0] = score(nums, 0);
scores[1] = score(nums, 1);
} else if (targetInd == N - 1) {
swap(nums, N - 2, N - 1);
scores[N - 2] = score(nums, N - 2);
scores[N - 1] = score(nums, N - 1);
} else {
int leftScore = 1 + nums[targetInd - 1] < targetInd ? - 1 : 1;
int rightScore = 1 + nums[targetInd + 1] > targetInd ? - 1 : 1;
if (leftScore > rightScore) {
swap(nums, targetInd - 1, targetInd);
scores[targetInd - 1] = score(nums, targetInd - 1);
scores[targetInd] = score(nums, targetInd);
} else {
swap(nums, targetInd, targetInd + 1);
scores[targetInd + 1] = score(nums, targetInd + 1);
scores[targetInd] = score(nums, targetInd);
}
}
addRemoveProblems(targetInd, problematics, nums);
nProbs = problematics.stream().count();
nSwap ++;
}
return nSwap;
}
private static void addRemoveProblems(int targetInd, List<Integer> problematics, int[] nums) {
if (targetInd == nums[targetInd]) {
problematics.add(targetInd);
} else {
problematics.remove(new Integer(targetInd));
}
if (targetInd != nums.length - 1) {
if (targetInd + 1 == nums[targetInd + 1]) {
problematics.add(targetInd + 1);
} else {
problematics.remove(new Integer(targetInd + 1));
}
}
if (targetInd != 0) {
if (targetInd - 1 == nums[targetInd - 1]) {
problematics.add(targetInd - 1);
} else {
problematics.remove(new Integer(targetInd - 1));
}
}
}
private static int score(int[] nums, int i) {
return Math.abs(i - nums[i]);
}
private static void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
public static void main(String[] args) {
// tests();
Scanner scanner = new Scanner(System.in);
int n = Integer.parseInt(scanner.nextLine());
int[] nums = new int[n];
String[] numsStr = scanner.nextLine().split(" ");
for (int i = 0; i < n; i ++) {
nums[i] = Integer.parseInt(numsStr[i]);
}
System.out.println(solve(n, nums));
}
private static String ex1 = "5\n1 4 3 5 2";
private static String ex2 = "2\n1 2";
private static String ex3 = "2\n2 1";
private static String ex4 = "9\n1 2 4 9 5 8 7 3 6";
private static void tests() {
System.out.println(solve(5, new int[]{1, 4, 3, 5, 2}));
System.out.println(solve(2, new int[]{1, 2}));
System.out.println(solve(2, new int[]{2, 1}));
System.out.println(solve(9, new int[]{1, 2, 4, 9, 5, 8, 7, 3, 6}));
}
}
Submission Info
Submission Time |
|
Task |
D - Derangement |
User |
gavotte |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
0 |
Code Size |
4002 Byte |
Status |
TLE |
Exec Time |
2109 ms |
Memory |
50308 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt |
All |
0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt |
Case Name |
Status |
Exec Time |
Memory |
0_000.txt |
AC |
221 ms |
27988 KB |
0_001.txt |
AC |
163 ms |
26836 KB |
0_002.txt |
AC |
175 ms |
24788 KB |
0_003.txt |
AC |
171 ms |
26964 KB |
1_004.txt |
AC |
173 ms |
26580 KB |
1_005.txt |
TLE |
2109 ms |
48052 KB |
1_006.txt |
TLE |
2109 ms |
50308 KB |
1_007.txt |
AC |
371 ms |
47096 KB |
1_008.txt |
TLE |
2109 ms |
48968 KB |
1_009.txt |
TLE |
2109 ms |
50260 KB |
1_010.txt |
AC |
372 ms |
47136 KB |
1_011.txt |
TLE |
2109 ms |
45784 KB |
1_012.txt |
TLE |
2109 ms |
46636 KB |
1_013.txt |
TLE |
2109 ms |
48236 KB |
1_014.txt |
AC |
363 ms |
44832 KB |