Submission #260522

#	Time	Username	Problem	Language	Result	Execution time	Memory
260522		idk321	Arranging Shoes (IOI19_shoes)	Java	10 / 100	1098 ms	42320 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>[] rightShoes = new ArrayDeque[n + 1];
		for (int i = 1; i < n; i++) rightShoes[i] = new ArrayDeque<Integer>();

		int currentFree = 0;
		int swaps = 0;
		ArrayList<Integer> shoes = new ArrayList<Integer>();
		for (int i = 0; i < n; i++) shoes.add(s[i]);
		for (int i = 0; i < n; i += 2) {
			int shoe = 0;
			for (int j = i; j < n; j++) {
				if (shoes.get(j) < 0) {
					swaps += j - i;
					shoe = shoes.get(j);
					shoes.remove(j);
					shoes.add(i, shoe);
					break;
				}
			}
			for (int j = i + 1; j < n; j++) {
				if (shoes.get(j) == shoe * (-1)) {
					swaps += j - (i + 1);
					int rightShoe = shoes.get(j);
					shoes.remove(j);
					shoes.add(i + 1, rightShoe);
					break;
				}
			}

		}
		//System.out.println(shoes);

		return swaps;
	}
}

Compilation message (stderr)

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

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