Submission #245689

#	Time	Username	Problem	Language	Result	Execution time	Memory
245689		luisoncpp	Arranging Shoes (IOI19_shoes)	C++17	30 / 100	217 ms	139892 KiB

shoes

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

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

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;
}

void Normalize(Vec<int>& S) {
	std::map<int, int> AbsToIndex;
	for (const int& num : S) {
		AbsToIndex[abs(num)] = 0;
	}
	int index = 1;
	for (auto& item : AbsToIndex) {
		item.second = index;
		++index;
	}
	for (auto& num : S) {
		int sign = num >= 0 ? 1 : -1;
		num = sign * AbsToIndex[abs(num)];
	}
}

Vec<int> GetFinalDestinations(const Vec<int>& NormS) {
	std::vector<Bucket> buckets(NormS.size() / 2 + 1);
	for (int i = 0; i < NormS.size(); ++i) {
		int num = NormS[i];
		if (num < 0) {
			buckets[-num].LeftIndex.push(i); 
		}
		if (num > 0) {
			buckets[num].RightIndex.push(i);
		}
	}
	Vec<int> 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<int>& S, const int start, const int size) {
	if (size < 2) {
		return 0;
	}
	ll count = 0;
	int izq = start;
	int der = start + size/2;
	int mid = der;
	int end = start + size;
	count += SortAndCountInversions(S, izq, size / 2);
	count += SortAndCountInversions(S, der, size - (size / 2));
	Vec<int> 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 (int i = 0; i < size; ++i) {
		S[start + i] = result[i];
	}
	return count;
}

ll 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<int> GetFinalDestinations(Vec<int>&)':
shoes.cpp:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < NormS.size(); ++i) {
                  ~~^~~~~~~~~~~~~~
shoes.cpp: In function 'll SortAndCountInversions(Vec<int>&, int, int)':
shoes.cpp:79:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (result.size() < size) {
         ~~~~~~~~~~~~~~^~~~~~

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