제출 #349837

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
349837		negiempire	Arranging Shoes (IOI19_shoes)	Java	0 / 100	72 ms	8808 KiB

shoes

public class shoes {

	public static void main(String[] args) {
		int testData[] = { -1, 1, -2, 2 };
		System.out.println("total count: " +count_swaps(testData));
	}

	int[] a;
	
	public shoes() {
		
	}

	public shoes(int n) {
		a = new int[n];
	}

	int count(int right) {
		int cnt = 0;
		for (; right >= 0; right = (right & (right + 1)) - 1) {
			cnt += a[right];
		}
		return cnt;
	}

	int count(int left, int right) {
		return count(right) - count(left - 1);
	}

	void put(int index) {
		for (; index < a.length; index = index | (index + 1)) {
			a[index]++;
		}
	}

	static int[] change(int[] v) {
		int n = v.length / 2;
		int cnt[] = new int[n];
		for (int i = 0; i < 2 * n; i++)
			if (v[i] > 0)
				cnt[v[i] - 1]++;

		for (int i = 1; i < n; i++)
			cnt[i] += cnt[i - 1];

		int[] cntl = cnt, cntr = cnt;

		for (int i = 0; i < 2 * n; i++)
			if (v[i] > 0)
				v[i] = (--cntr[v[i] - 1]) + 1;
			else
				v[i] = -((--cntl[-v[i] - 1]) + 1);
		return v;
	}

	static int[] create_index(int n, int[] S) {
		int[] index = new int[2 * n + 1];
		for (int i = 0; i < 2 * n; i++) {
			index[S[i] + n] = i;
		}
		return index;
	}

	static long count_adjacent(int n, int[] S) {
		int[] index = create_index(n, S);
		shoes f = new shoes(2 * n);
		long ans = 0;
		for (int i = 0; i < 2 * n; i++) {
			if (S[i] != 0) {
				int pos = index[-S[i] + n];
				ans += pos - i - f.count(i, pos) - (S[i] < 0 ? 1 : 0);
				S[pos] = 0;
				f.put(pos);
			}
		}
		return ans;
	}

	static long count_swaps(int[] S) {
		S = change(S);
		int n = S.length / 2;
		return count_adjacent(n, S);
	}

}

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