Submission #1067858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067858		Gromp15	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	26 ms	4044 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; }

struct fenwick {
	int n; vector<int> bit;
	fenwick(int a) : n(a), bit(a+1) {}
	void update(int pos, int x) {
		pos++;
		for (int i = pos; i <= n; i += i&-i) bit[i] += x;
	}
	int sum(int pos) {
		int res = 0;
		while (pos) res += bit[pos], pos -= pos&-pos;
		return res;
	}
	int query(int l, int r) {
		return sum(r+1) - sum(l);
	}
};

long long count_swaps(std::vector<int> s) {
	int n = sz(s);
	bool sm = 1;
	for (int i = 1; i < n; i++) sm &= abs(s[i]) == abs(s[0]);
	if (sm) {
		fenwick fw(n);
		int A = 0, B = 1;
		ll inv = 0;
		for (int i = 0; i < n; i++) {
			int pos;
			if (s[i] < 0) pos = A, A += 2;
			else pos = B, B += 2;
			inv += pos+1 < n ? fw.query(pos+1, n-1) : 0;
			fw.update(pos, 1);
		}
		return inv;
	}
	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: 20 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15