| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 172272 | ijxjdjd | Arranging Shoes (IOI19_shoes) | Java | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
public class shoes {
static long count_swaps(int[] S) {
int N = S.length/2;
ArrayDeque<Integer>[] left = new ArrayDeque[N];
ArrayDeque<Integer>[] right = new ArrayDeque[N];
for (int i = 0; i < N; i++) {
left[i] = new ArrayDeque<>();
right[i] = new ArrayDeque<>();
}
FenwickTree unset = new FenwickTree(2 * N);
for (int i = 0; i < 2 * N; i++) {
int a = S[i];
if (a < 0) {
left[(-a) - 1].add(i);
} else {
right[a - 1].add(i);
}
unset.add(i, 1);
}
long res = 0;
PriorityQueue<int[]> next = new PriorityQueue<>(new Comparator<int[]>() {
public int compare(int[] ints, int[] t1) {
return Integer.compare(ints[0] + ints[1] + (ints[0] > ints[1] ? 1 : 0), t1[0] + t1[1] + (t1[0] > t1[1] ? 1 : 0));
}
});
for (int i = 0; i < N; i++) {
if (left[i].size() > 0) {
next.add(new int[]{left[i].remove(), right[i].remove(), i});
}
}
for (int i = 0; i < N; i++) {
int[] a = next.remove();
res += (unset.sum(a[0]) - 1);
unset.add(a[0], -1);
res += (unset.sum(a[1]) - 1);
unset.add(a[1], -1);
if (left[a[2]].size() > 0) {
next.add(new int[]{left[a[2]].remove(), right[a[2]].remove(), a[2]});
}
}
return res;
}
static class FenwickTree {
public int[] BIT;
public int size = 0;
public FenwickTree(int N) {
BIT = new int[N];
size = N;
}
public FenwickTree(int[] arr) {
size = arr.length;
BIT = new int[arr.length];
for (int i = 0; i < size; i++) {
add(i, arr[i]);
}
}
public void add(int id, int add) {
for (int i = id; i < size; i |= i + 1) {
BIT[i] += add;
}
}
public int sum(int r) {
if (r < 0 || r >= size) {
return 0;
}
int res = 0;
for (int i = r; i >= 0; i = ((i) & (i + 1)) - 1) {
res += BIT[i];
}
return res;
}
}
}