Submission #1067853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067853		Gromp15	Arranging Shoes (IOI19_shoes)	C++17	30 / 100	13 ms	3248 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#define ll long long
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

long long count_swaps(std::vector<int> s) {
	int n = sz(s);
	if (n / 2 <= 8) {
		vector<int> who;
		for (int i = 0; i < n; i++) {
			if (s[i] < 0) who.emplace_back(s[i]);
		}
		sort(all(who));
		ll ans = 1e18;
		do {
			vector<bool> vis(n);
			vector<int> where(n);
			for (int i = 0; i < n; i++) {
				int fd = who[i / 2] * (i % 2 == 0 ? 1 : -1);
				for (int j = 0; j < n; j++) {
					if (s[j] == fd && !vis[j]) {
						vis[j] = 1, where[i] = j; break;
					}
				}
			}
			ll inv = 0;
			for (int i = 0; i < n; i++) for (int j = i+1; j < n; j++) inv += where[i] > where[j];
			ckmin(ans, inv);
		}
		while (next_permutation(all(who)));
		return ans;
	}
	return 0;
}

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