| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 609640 | fvogel499 | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "grader.cpp"
#include "shoes.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define vi vector<int>
#define size(x) (int)((x).size())
#define int long long
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int p2 = 1<<17;
struct Segtree {
Segtree() {
t = new int [p2*2];
for (int i = 0; i < p2*2; i++) t[i] = 0;
}
void upd(int x, int v) {
for (x += p2; x; x /= 2) {
t[x] += v;
}
}
int get(int b, int e) {
int r = 0;
b += p2;
e += p2;
while (b <= e) {
if (b%2 == 1) {
r += t[b];
b++;
}
if (e%2 == 0) {
r += t[e];
e--;
}
b /= 2;
e /= 2;
}
return r;
}
int* t;
};
int count_swaps(vector<signed> bcc) {
vi b;
for (int i : bcc) b.push_back(i);
int n = size(b);
map<int, map<int, vi>> per;
for (int i = n-1; i >= 0; i--) {
int sign = 0;
if (b[i] < 0) {
sign = 1;
}
per[abs(b[i])][sign].push_back(i);
}
bool handled [n];
for (int i = 0; i < n; i++) handled[i] = false;
Segtree st = Segtree();
int cost = 0;
int before = 0;
for (int i = 0; i < n; i++) if (!handled[i]) {
int sign = 0;
if (b[i] < 0) {
sign = 1;
}
assert(size(per[abs(b[i])][sign]) == size(per[abs(b[i])][!sign]));
assert(!per[abs(b[i])][sign].empty() && per[abs(b[i])][sign].back() == i);
per[abs(b[i])][sign].pop_back();
int j = per[abs(b[i])][!sign].back();
per[abs(b[i])][!sign].pop_back();
if (b[i] > 0) {
cost++;
}
if (i+1 <= j-1) {
int loc = st.get(i+1, j-1);
cost += (j-1)-(i+1)+1 - loc;
}
st.upd(i, 1); // not needed
st.upd(j, 1);
handled[i] = true;
handled[j] = true;
}
return cost;
}