| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1070684 | kiethm07 | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pii pair<int,int>
#define iii pair<int,pii>
#define fi first
#define se second
#define vi vector<int>
#define vii vector<pii>
#define pb(i) push_back(i)
#define all(x) x.begin(),x.end()
#define TEXT "a"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int inf = 1e9 + 7;
const ld eps = 1e-8;
const double pi = acos(-1);
const int N = 1e5 + 5;
class BIT{
private:
vector<int> bit;
int n;
public:
BIT(int m){
n = m;
bit.resize(n + 5,0);
}
void update(int i,int v){
while(i <= n){
bit[i] += v;
i += i & (-i);
}
}
int get(int i){
int res = 0;
while(i > 0){
res += bit[i];
i -= i & (-i);
}
return res;
}
};
deque<int> c[N][2];
ll count_swaps(vector<int>& a){
int n = a.size();
ll res = 0;
vector<bool> mark(n + 5,0);
for (int i = 0; i < n; i++){
c[i][0].clear();
c[i][1].clear();
}
for (int i = 0; i < n; i++){
bool f = a[i] > 0;
int t = abs(a[i]);
c[t][f].push_back(i + 1);
}
BIT bit(n);
for (int i = 0; i < n; i++){
if (mark[i]) continue;
mark[i] = 1;
bool f = a[i] > 0;
int t = abs(a[i]);
int pre = c[t][1 ^ f].front();
c[t][1 ^ f].pop_front();
c[t][f].pop_front();
mark[pre - 1] = 1;
int id = pre - bit.get(pre) - 1;
res += id - 1 + f;
//cout << i << " " << id << " " << pre << " " << bit.get(pre) << " " << res << "\n";
bit.update(pre,1);
bit.update(i + 1,1);
}
return res;
}