Submission #421799

#	Time	Username	Problem	Language	Result	Execution time	Memory
421799		KoD	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	359 ms	26796 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<int>> map;
	for (int i = n - 1; i >= 0; --i) {
		map[s[i]].push_back(i);
	}
	Vec<char> done(n);
	Vec<int> p(n);
	int idx = 0;
	for (int i = 0; i < n; ++i) {
		if (done[i]) continue;
		map[s[i]].pop_back();
		const auto j = map[-s[i]].back();
		map[-s[i]].pop_back();
		done[i] = done[j] = true;
		if (s[i] > 0) {
			p[idx++] = j;
			p[idx++] = i;
		} else {
			p[idx++] = i;
			p[idx++] = j;
		}
	}
	ll ret = 0;
	Fenwick fen(n);
	for (const auto i: p) {
		ret += fen.fold(i, n);
		fen.add(i, 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