Submission #245723

#	Time	Username	Problem	Language	Result	Execution time	Memory
245723		luisoncpp	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	698 ms	146200 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 = 0;
	for (int& num : S) {
		int sign = num >= 0 ? 1 : -1;
		if (!UnmatchedValue[-num].empty()) {
			auto prev_num = num;
			// num = sign * UnmatchedValue[-num].front();
			int val = UnmatchedValue[-num].front();
			if (sign < 0) {
				num = 2 * val;
			} else {
				num = 2 * val + 1;
			}
			UnmatchedValue[-prev_num].pop();
		} else {
			UnmatchedValue[num].push(index);
			// num = sign * index;
			if (sign < 0) {
				num = 2 * index;
			} else {
				num = 2 * index + 1;
			}
			++index;
		}
	}
}

ll SortAndCountInversions(Vec<int>& 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<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 (ll i = 0; i < size; ++i) {
		S[start + i] = result[i];
	}
	return count;
}

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

Compilation message (stderr)

shoes.cpp: In function 'll SortAndCountInversions(Vec<int>&, ll, ll)':
shoes.cpp:67: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