| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 847435 | Amaarsaa | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll Sum[800005], mid;
void Change(ll p, ll lo, ll hi, ll x) {
if ( lo== hi) {
Sum[x] = 1;
return ;
}
mid = (lo + hi)/2;
if ( x <= mid) Change(2 * p, lo, mid, x);
else Change(2 * p + 1, mid + 1, hi, x);
Sum[p] = Sum[2 * p] + Sum[2 * p + 1];
}
ll Find(ll p, ll lo, ll hi, ll st, ll fn) {
if ( st > hi || lo > fn) return 0;
if ( st <= lo && hi <= fn) {
return Sum[p];
}
mid = (lo + hi)/2;
return Find(2 * p, lo, mid, st, fn) + Find(2 * p + 1, mid + 1, hi, st, fn);
}
long long count_swaps(std::vector<int> s) {
ll n, i, p, m;
n = s.size();
int Used[100005];
queue < int > Left[n + 2], Right[n + 2];
for (i = 0; i < s.size(); i ++) {
cout << s[i] << " ";
if ( s[i] < 0) {
Left[-s[i]].push(i);
}
else Right[s[i]].push(i);
}
long long ans =0;
for (i = 0; i < s.size(); i ++) {
if ( Used[i] == 1) continue;
p = s[i];
if ( p < 0) {
m= Right[-p].front();
Used[m]= 1;
m = m + Find(1, 0, n - 1, m, n - 1);
ans += (m - i - 1);
Right[-p].pop();
}
else {
cout << p << " " << Left[p].size() << endl;
m= Left[p].front();
Used[m]= 1;
m = m + Find(1, 0, n - 1, m, n - 1);
ans += (m - i );
Left[-p].pop();
}
}
return ans;
}
int main() {
ll n, i, x;
vector < int > V;
cin >> n;
for (i = 1; i <= n; i ++) {
cin >> x;
V.push_back(x);
}
cout << count_swaps(V) << endl;
}