Submission #245726

#	Time	Username	Problem	Language	Result	Execution time	Memory
245726		luisoncpp	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	705 ms	146040 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>;

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

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

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

Compilation message (stderr)

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