Submission #542731

#	Time	Username	Problem	Language	Result	Execution time	Memory
542731		collodel	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	112 ms	8636 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <iterator>
#include <map>

using namespace std;
using ll = signed long long int;

ll merge_sort(vector<int>& a) {
	if(a.size() == 1) return 0;

	vector<int> l(a.size()/2), r(a.size() - a.size()/2);
	copy(a.begin(), a.begin() + a.size()/2, l.begin());
	copy(a.begin() + a.size()/2, a.end(), r.begin());

	ll ans = merge_sort(l) + merge_sort(r);

	int i = 0, j = 0;
	while(i < (int)l.size() && j < (int)r.size()) {
		if(l[i] <= r[j]) a[i+j] = l[i], i++;
		else ans += l.size() - i, a[i+j] = r[j], j++;
	}

	while(i < (int)l.size()) a[i+j] = l[i], i++;
	while(j < (int)r.size()) a[i+j] = r[j], j++;

	return ans;
}

long long count_swaps(std::vector<int> a) {
	int n = a.size(), x = 0;
	vector<int> idx(n);

	multimap<int, int> pairs;

	for(int i = 0; i < n; ++i) {
		if(pairs.count(a[i])) {
			auto it = pairs.lower_bound(a[i]);
			idx[i] = it->second + (a[i] > 0);
			pairs.erase(it);
		} else {
			idx[i] = x + (a[i] > 0);
			pairs.emplace(-a[i], x);
			x += 2;
		}
	}

	return merge_sort(idx);
}

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