Submission #349868

#	Time	Username	Problem	Language	Result	Execution time	Memory
349868		negiempire	Arranging Shoes (IOI19_shoes)	Java	100 / 100	236 ms	15652 KiB

shoes

public class shoes {

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

	static int[] a;
	
	public shoes() {
		
	}

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

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

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

	static 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<cnt.length; i++)
			cnt[i] = 0;
		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 = new int[cnt.length];//cnt, cntr = cnt;
		int[] cntr = new int[cnt.length];
		copyArray(cnt,  cntl);
		copyArray(cnt,  cntr);
		
		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 void copyArray(int[] a1,int[] a2) {
		for (int i=0; i<a1.length; i++) {
			a2[i] =  a1[i];
		}
	}
	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 - count(i, pos) - (S[i] < 0 ? 1 : 0);
				S[pos] = 0;
				put(pos);
			}
		}
		return ans;
	}

	static long count_swaps(int[] S) {
		S = change(S);
		int n = S.length / 2;
		a = new int[2*n];
		for (int i =0; i < a.length; i++)
			a[i] = 0;
		return count_adjacent(n, S);
	}

}

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