| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 222882 | MrDomino | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
///#include "shoes.h"
using namespace std;
typedef long long ll;
ll get_dist(vector<int> ord)
{
int n = (int) ord.size();
vector<int> aib(n + 1);
ll sol = 0;
for (int i = 0; i < n; i++)
{
sol += i;
int x = ord[i] + 1, y = x;
while (x)
{
sol -= aib[x];
x -= x & (-x);
}
x = y;
while (x <= n)
{
aib[x]++;
x += x & (-x);
}
}
return sol;
}
const int N = (int) 1e5 + 7;
vector<int> pl[N];
vector<int> mn[N];
struct T
{
int l;
int r;
};
bool operator < (T a, T b)
{
return a.l + a.r < b.l + b.r;
}
long long count_swaps(vector<int> a)
{
int n = (int) a.size() / 2;
for (int i = 0; i < 2 * n; i++)
{
pl[a[i]].push_back(i);
mn[-a[i]].push_back(i);
}
vector<T> p;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < (int) pl[i].size(); j++)
{
p.push_back({mn[i][j], pl[i][j]});
}
}
sort(p.begin(), p.end());
vector<int> ord;
for (auto &it : p)
{
ord.push_back(it.l);
ord.push_back(it.r);
}
return get_dist(ord);
}
int main()
{
cout << count_swaps({2, 1, -1, -2});
}