Submission #1243895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243895		inkvizytor	Arranging Shoes (IOI19_shoes)	C++20	25 / 100	394 ms	147460 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll merge_sort(vector<int> &a, int p, int k) {
	if (p == k) {
		return 0;
	}
	ll x = merge_sort(a, p, (p+k)/2)+merge_sort(a, (p+k)/2+1, k);
	int r = (p+k)/2-p+1;
	queue<int> s;
	int in1 = p, in2 = (p+k)/2+1;
	while (in1 <= (p+k)/2 && in2 <= k) {
		if (in1 > (p+k)/2) {
			s.push(a[in2]);
			in2++;
			x += r;
			continue;
		}
		if (in2 > k) {
			s.push(a[in1]);
			in1++;
			continue;
		}
		if (a[in1] < a[in2]) {
			s.push(a[in1]);
			in1++;
			r--;
		}
		else {
			x += r;
			s.push(a[in2]);
			in2++;
		}
	}
	return x;
}

long long count_swaps(std::vector<int> s) {
	int n = s.size();
	map<int, queue<int>> mp;
	for (int i = 0; i < n; i++) {
		mp[s[i]].push(i);
	}
	vector<int> p (n, 0);
	vector<bool> odw (n, 0);
	int l = 0;
	for (int i = 0; i < n; i++) {
		if (odw[i]) continue;
		int j = mp[-s[i]].front();
		mp[-s[i]].pop();
		mp[s[i]].pop();
		odw[i] = 1;
		odw[j] = 1;
		if (s[i] < 0) {
			p[i] = l;
			p[j] = l+1;
		}
		else {
			p[j] = l;
			p[i] = l+1;
		}
		l +=2;
	}
	return merge_sort(p, 0, n-1);
}

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