Submission #245696

#	Time	Username	Problem	Language	Result	Execution time	Memory
245696		luisoncpp	Arranging Shoes (IOI19_shoes)	C++17	Compilation error	0 ms	0 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<ll> LeftIndex;
	std::queue<ll> RightIndex;
};

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

Vec<ll> GetFinalDestinations(const Vec<ll>& 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[-num].LeftIndex.push(i); 
		}
		if (num > 0) {
			buckets[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) {
	ll count = 0;
	for (int i = 0; i < S.size(); ++i) {
		for (int k = 0; k < i; ++k) {
			if (S[k] > S[i]) {
				++count;
			}
		}
	}
	return count;

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

Compilation message (stderr)

shoes.cpp: In function 'Vec<long int> GetFinalDestinations(Vec<long int>&)':
shoes.cpp:45: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:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); ++i) {
                  ~~^~~~~~~~~~
shoes.cpp:89:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (result.size() < size) {
         ~~~~~~~~~~~~~~^~~~~~
/tmp/cczufYED.o: In function `main':
grader.cpp:(.text.startup+0x282): undefined reference to `count_swaps(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status