| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 922083 | Nurislam | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include "grader.cpp"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define order_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
long long count_swaps(std::vector<int> a) {
int n = a.size()/2;
int la[n*2]{};
queue<int> pos[n+1], neg[n+1];
for(int i = 0; i < n*2; i++){
int x = a[i];
if(x < 0){
if(!pos[-a[i]].empty()){
la[pos[-a[i]].front()] = i;
pos[-a[i]].pop();
}else{
neg[-a[i]].push(i);
}
}else{
if(!neg[a[i]].empty()){
la[neg[a[i]].front()] = i;
neg[a[i]].pop();
}else{
pos[a[i]].push(i);
}
}
}
order_set st;
int ans = 0, us[n*2]{};
for(int i = 0; i < n*2; i++){
if(us[i]){
st.erase(i);
continue;
}
int r = st.order_of_key(la[i]);
if(r < (int)st.size() && *st.find_by_order(r) < la[a[i]])r++;
ans += la[i]-i-r;
if(a[i] < 0)ans--;
st.insert(la[i]);
us[la[i]]++;
}
return ans;
}