제출 #1243904

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243904		inkvizytor	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	375 ms	147556 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++;
		}
	}
	int in = p;
	while (!s.empty()) {
		a[in] = s.front();
		s.pop();
		in++;
	}
	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: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15