Submission #604174

#	Time	Username	Problem	Language	Result	Execution time	Memory
604174		MathStudent2002	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	109 ms	17700 KiB

shoes

#include "shoes.h"
#include <algorithm>

typedef long long ll;

const int MAXM = 200005;

ll BIT[MAXM];

void add(int i, ll delta) {
	while (i < MAXM) {
		BIT[i] += delta;
		i += (i & (-i));
	}
}

ll query(int i) {
	ll ans = 0;
	while (i > 0) {
		ans += BIT[i];
		i -= (i & (-i));
	}
	return ans;
}

long long count_swaps(std::vector<int> s) {
	int N = int(s.size()) / 2;
	std::vector<int> loc[2*N+2];
	for (int i = 0; i < 2*N; i++) {
		int shoe = s[i];
		if (shoe > 0) loc[shoe].push_back(i);
		else loc[-shoe+(N+1)].push_back(i);
	}

	std::vector<std::pair<int, int>> sloc;

	for (int i = 1; i <= N; i++) {
		for (int idx = 0; idx < int(loc[i].size()); idx++) {
			sloc.push_back({loc[i][idx] + loc[i+N+1][idx], i});
		}
	}

	std::sort(sloc.begin(), sloc.end());

	int perm[2*N];
	int id[N+1];
	for (int i = 0; i <= N; i++) {
		id[i] = 0;
	}

	for (int i = 0; i < N; i++) {
		int shoeid = sloc[i].second;
		perm[loc[N+1+shoeid][id[shoeid]]] = 2*i;
		perm[loc[shoeid][id[shoeid]]] = 2*i+1;
		id[shoeid]++;
	}

	// count inversions
	
	int M = 2 * N;
	
	ll ans = 0;
	for (int i = M-1; i >= 0; i--) {
		ans += query(perm[i]+1);
		add(perm[i]+1, 1);
	}

	return ans;
}

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