Submission #914110

#	Time	Username	Problem	Language	Result	Execution time	Memory
914110		lamter	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	481 ms	149652 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using i64 = long long int;

struct BIT {
	int n;
	std::vector <int> a;

	BIT(int _n = 0) : n(_n) {
		a.assign(n, 0);
	}

	void update(int x, int v) {
		for (; x < n; x |= x + 1)
			a[x] += v;
	}

	int get(int x) const {
		int ans = 0;
		for (; x >= 0; x = (x & (x + 1)) - 1)
			ans += a[x];
		return ans;
	}
};

i64 count_inversion(std::vector <int> a) {
	i64 ans = 0;
	int n = a.size();
	BIT bit(n);
	for (int i = 0; i < n; i += 1) {
		ans += i - bit.get(a[i]);
		bit.update(a[i], +1);
	}
	return ans;
}

i64 count_swaps(std::vector <int> a) {
	int n = (int) a.size();
	std::map <int, std::deque <int>> maps;
	int T = 0;
	std::vector <int> pos(n);
	for (int i = 0; i < n; i += 1) {
		int x = a[i];
		if (maps[-x].empty()) {
			maps[x].push_back(T + (x > 0));
			pos[i] = T + (x > 0);
			T += 2;
		} else {
			pos[i] = maps[-x].front() + (x > 0 ? +1 : -1);
			maps[-x].pop_front();
		}
	}
	return count_inversion(pos);
}

#ifdef ILOVELAMTER
	int main(void) {
		std::cout << count_swaps({4, -4}) << '\n';
		return 0;
	}
#endif // ILOVELAMTER

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