제출 #260546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
260546		idk321	Arranging Shoes (IOI19_shoes)	Java	100 / 100	634 ms	81436 KiB

shoes

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;

public class shoes {
	private int[] tree;

	private void add(int from, int to, int a, int b, int node) {
		if (from <= a && b <= to) {
			tree[node]++;
			return;
		}

		int mid = (a + b) / 2;
		if (from <= mid) {
			add(from, to, a, mid, node * 2);
		}
		if (to > mid) {
			add(from, to, mid + 1, b, node * 2 + 1);
		}
	}

	private int getSum(int i, int a, int b, int node) {
		if (a == b) {
			return tree[node];
		}


		int mid = (a + b) / 2;
		if (i <= mid) return getSum(i, a, mid, node * 2) + tree[node];
		return getSum(i, mid + 1, b, node * 2 + 1) + tree[node];
	}

	public long count_swaps(int[] s) {
		int n = s.length;
		ArrayDeque<Integer>[] shoes = new ArrayDeque[2 * n + 1];
		for (int i = 0; i <= 2 * n; i++) shoes[i] = new ArrayDeque<Integer>();

		for (int i = 0; i < n; i++) {
			shoes[s[i] + n].addLast(i);
		}

		tree = new int[4 * n];

		long swaps = 0;
		for (int i = 0; i < n; i++) {
			if (shoes[n + s[i]].isEmpty()  || shoes[n + s[i]].peekFirst() != i) continue;
			//System.out.println(i);
			int index1 = getSum(i, 0, n - 1, 1) + i;
			shoes[n + s[i]].removeFirst();
			int orgIndex2 = shoes[n - s[i]].removeFirst();
			int index2 = getSum(orgIndex2, 0, n - 1, 1) + orgIndex2;
			swaps += index2 - index1;
			if (s[i] < 0) swaps--;
			add(0, orgIndex2, 0, n - 1, 1);
		}

		return swaps;
	}
}

컴파일 시 표준 에러 (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