# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1208334 | Gabp | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
long long int count_swaps(vetor<int> S) {
int n = S.size() / 2;
int cnt = 0;
vector<int> idx(n + 1, -1);
for (int i = 0; i < 2 * n; i++) {
int x = abs(S[i]);
if (idx[x] != -1) {
S[i] = 2 * idx[x] + (S[i] > 0);
}
idx[x] = cnt++;
S[i] = 2 * cnt - 2 + (S[i] < 0);
}
long long int ans = 0;
auto solve = [&](auto self, int l, int r) -> void {
if (l == r) return;
int mid = l + (r - l) / 2;
self(self, l, mid);
self(self, mid + 1, r);
int p1 = l, p2 = mid + 1;
vector<int> a;
while (p1 <= mid || p2 <= r) {
if (p1 > mid) a.push_back(S[p2++]);
else if (p2 > r) a.push_back(S[p1++]);
else if (S[p1] < S[p2]) a.push_back(S[p1++]);
else {
a.push_back(S[p2++]);
ans += mid + 1 - p1;
}
}
for (int i = l; i <= r; i++) S[i] = a[i - l];
};
solve(solve, 0, 2 * n - 1);
return ans;
}