Submission #587004

#	Time	Username	Problem	Language	Result	Execution time	Memory
587004		Zanite	Arranging Shoes (IOI19_shoes)	C++17	30 / 100	1095 ms	292276 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

using ll	= long long;
using pii	= pair<int, int>;
using pll	= pair<ll, ll>;

const ll INF	= 1e18;

#define fi	first
#define se	second

ll count_swaps(vector<int> s) {
	int n = s.size();

	vector<int> perm;
	map<int, deque<int>> occ;
	for (int i = 0; i < n; i++) {
		if (s[i] > 0) perm.push_back(s[i]);
		occ[s[i]].push_back(i);
	}
	sort(perm.begin(), perm.end());

	ll ans = INF;
	do {
		vector<int> rel(n);
		map<int, deque<int>> tocc = occ;

		int placed = 0;
		for (auto i : perm) {
			rel[tocc[-i].front()] = placed++;
			tocc[-i].pop_front();

			rel[tocc[i].front()] = placed++;
			tocc[i].pop_front();
		}

		ll cur = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i; j > 0; j--) {
				if (rel[j] < rel[j-1]) {
					swap(rel[j], rel[j-1]);
					cur++;
				}
			}
		}
		ans = min(ans, cur);
	} while (next_permutation(perm.begin(), perm.end()));

	return ans;
}

// Grader

#ifdef Zanite

int main() {
	int n;
	assert(1 == scanf("%d", &n));
	vector<int> S(2 * n);
	for (int i = 0; i < 2 * n; i++)
		assert(1 == scanf("%d", &S[i]));
	fclose(stdin);

	long long result = count_swaps(S);

	printf("%lld\n", result);
	fclose(stdout);
	return 0;
}

#endif

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