Submission #420400

#	Time	Username	Problem	Language	Result	Execution time	Memory
420400		KoD	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	228 ms	16028 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

using ll = long long;
template <class T> using Vec = std::vector<T>;

struct Fenwick {
	Vec<int> data;
	Fenwick(const int n): data(n + 1) {}
	void add(int i, const int x) {
		for (i += 1; i < (int) data.size(); i += i & -i) {
			data[i] += x;
		}
	}
	int get(int i) const {
		int x = 0;
		for (; i > 0; i -= i & -i) {
			x += data[i];
		}
		return x;
	}
	int fold(const int l, const int r) const {
		return get(r) - get(l);
	}
};

ll count_swaps(Vec<int> s) {
	const int n = (int) s.size();
	std::map<int, Vec<std::pair<int, bool>>> map;
	for (int i = 0; i < n; ++i) {
		if (s[i] > 0) {
			map[s[i]].emplace_back(i, true);
		} else {
			map[-s[i]].emplace_back(i, false);
		}
	}
	ll ret = 0;
	Fenwick fen(n + 1);
	Vec<std::pair<int, int>> pair;
	for (const auto& [x, vec] : map) {
		const int m = (int) vec.size();
		int pos = 0, neg = 0;
		Vec<int> assign(m);
		for (int i = 0; i < m; ++i) {
			const auto [j, f] = vec[i];
			if (f) {
				assign[2 * pos + 1] = i;
				pos += 1;
			} else {
				assign[2 * neg] = i;
				neg += 1;
			}
		}
		for (int i = 0; i < m / 2; ++i) {
			const int l = 2 * i;
			const int r = 2 * i + 1;
			if (vec[assign[l]].first > vec[assign[r]].first) {
				ret += 1;
				std::swap(assign[l], assign[r]);
			}
			pair.emplace_back(vec[assign[l]].first, vec[assign[r]].first);
		}
	}
	std::sort(pair.begin(), pair.end());
	for (const auto [l, r]: pair) {
		ret += fen.fold(0, l + 1);
		ret += fen.fold(0, r + 1);
		fen.add(l + 1, 1);
		fen.add(r, -1);
	}
	
	return ret;
}

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