제출 #526540

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
526540		ITO	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	180 ms	140176 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, va[200000];
vector<int> v;
pair<queue<int>, queue<int>> pa[100001];
ll eat(int l, int r) {
	if (l + 1 == r) return 0;
	int mi = (l + r) / 2, i = l, j = mi, k = l;
	ll an = eat(l, mi) + eat(mi, r);
	while (i < mi && j < r) {
		if (v[i] < v[j]) {
			va[k++] = v[i++];
		} else {
			va[k++] = v[j++];
			an = an + mi - i;
		}
	}
	while (i < mi) va[k++] = v[i++];
	while (j < r) va[k++] = v[j++];
	for (int ii = l; ii < r; ii++) v[ii] = va[ii];
	return an;
}
ll count_swaps(std::vector<int> s) {
	n = s.size();
	for (int i = 0; i < n; i++) {
		if (s[i] < 0) {
			pa[-s[i]].first.push(i);
		} else {
			pa[s[i]].second.push(i);
		}
	}
	for (int i = 0; i < n; i++) {
		if (s[i] < 0) {
			v.push_back(i);
			v.push_back(pa[-s[i]].second.front());
			s[pa[-s[i]].second.front()] = 0;
			pa[-s[i]].first.pop();
			pa[-s[i]].second.pop();
		} else if (s[i] > 0) {
			v.push_back(pa[s[i]].first.front());
			v.push_back(i);
			s[pa[s[i]].first.front()] = 0;
			pa[s[i]].first.pop();
			pa[s[i]].second.pop();
		}
	}
	return eat(0, n);
}

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