Submission #245720

#	Time	Username	Problem	Language	Result	Execution time	Memory
245720		luisoncpp	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	850 ms	147320 KiB

shoes

#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdint>
#include <cstdlib>
#include <cassert>
#include <queue>
#include <map>

using ll = int64_t;
template<typename T>
using Vec = std::vector<T>;

template<typename T>
void Debug(const Vec<T>& A) {
	for (const auto& item : A) {
		std::cout << item << " ";
	}
	std::cout << std::endl;
}

struct Bucket {
	std::queue<int> LeftIndex;
	std::queue<int> RightIndex;
};

void Normalize(Vec<int>& S) {
	std::map<int, std::queue<int>> UnmatchedValue;
	int index = 1;
	for (int& num : S) {
		int sign = num >= 0 ? 1 : -1;
		if (!UnmatchedValue[-num].empty()) {
			auto prev_num = num;
			num = sign * UnmatchedValue[-num].front();
			UnmatchedValue[-prev_num].pop();
		} else {
			UnmatchedValue[num].push(index);
			num = sign * index;
			++index;
		}
	}
}

Vec<ll> GetFinalDestinations(const Vec<int>& NormS) {
	std::vector<Bucket> buckets(NormS.size() / 2 + 1);
	for (ll i = 0; i < NormS.size(); ++i) {
		ll num = NormS[i];
		if (num < 0) {
			buckets.at(-num).LeftIndex.push(i); 
		}
		if (num > 0) {
			buckets.at(num).RightIndex.push(i);
		}
	}
	Vec<ll> ret;
	for (Bucket& b : buckets) {
		assert(b.LeftIndex.size() == b.RightIndex.size());
		while (!b.LeftIndex.empty()) {
			ret.push_back(b.LeftIndex.front());
			ret.push_back(b.RightIndex.front());
			b.LeftIndex.pop();
			b.RightIndex.pop();
		}
	}
	return ret;
}

ll SortAndCountInversions(Vec<ll>& S, const ll start, const ll size) {
	if (size < 2) {
		return 0;
	}
	ll count = 0;
	ll izq = start;
	ll der = start + size/2;
	ll mid = der;
	ll end = start + size;
	count += SortAndCountInversions(S, izq, size / 2);
	count += SortAndCountInversions(S, der, size - (size / 2));
	Vec<ll> result;
	while (result.size() < size) {
		bool insert_left = true;
		if (izq >= mid || (der < end && S[der] < S[izq])) {
			insert_left = false;
		}
		if (insert_left) {
			result.push_back(S[izq]);
			++izq;
		} else {
			result.push_back(S[der]);
			count += mid - izq;
			++der;
		}
	}
	for (ll i = 0; i < size; ++i) {
		S[start + i] = result[i];
	}
	return count;
}

int count_swaps(Vec<int> S) {
	Normalize(S);
	auto dest = GetFinalDestinations(S);
	return SortAndCountInversions(dest, 0, dest.size());
}

Compilation message (stderr)

shoes.cpp: In function 'Vec<long int> GetFinalDestinations(Vec<int>&)':
shoes.cpp:46:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (ll i = 0; i < NormS.size(); ++i) {
                 ~~^~~~~~~~~~~~~~
shoes.cpp: In function 'll SortAndCountInversions(Vec<long int>&, ll, ll)':
shoes.cpp:80:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (result.size() < size) {
         ~~~~~~~~~~~~~~^~~~~~

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