제출 #172273

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
172273		ijxjdjd	Arranging Shoes (IOI19_shoes)	Java	100 / 100	535 ms	45872 KiB

shoes

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.nio.Buffer;
import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class shoes {
    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;
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

Note: shoes.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15