| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 988282 | kachim2 | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <vector>
#include <queue>
#include <iostream>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
long long count_swaps(std::vector<int> s) {
std::vector<int> pos(s.size(), INT_MIN);
std::vector<int> spos(s.size());
std::vector<int> rpos(s.size());
for (int i = 0; i < s.size(); i++) {
spos[i] = i;
}
for (int i = 0; i < s.size(); i++) {
rpos[i] = i;
}
auto qm = new std::queue<int>[100007];
auto qp = new std::queue<int> [100007];
for (int i = 0; i < s.size(); i++) {
if (s[i] < 0) {
if (qp[-s[i]].empty()) {
qm[-s[i]].push(i);
} else {
auto x = qp[-s[i]].front();
qp[-s[i]].pop();
pos[i] = x;
}
} else {
if (qm[s[i]].empty()) {
qp[s[i]].push(i);
} else {
auto x = qm[s[i]].front();
qm[s[i]].pop();
pos[i] = x;
}
}
}
long count = 0;
// for (auto i : spos) {
// std::cerr << i << ' ';
//}
tree<int, null_type, std::less<int>, rb_tree_tag,
tree_order_statistics_node_update>
B;
for (int i = 0; i < s.size(); i++) {
B.insert(i*3+1);
}
for (int i = 0; i < s.size(); i++) {
if (pos[i] >= 0) {
if (s[i] > 0) {
count +=
B.order_of_key(i * 3 + 1) - B.order_of_key(pos[i] * 3 + 1) - 1;
B.erase(i * 3 + 1);
B.insert(pos[i]*3+2);
} else {
count +=
B.order_of_key(i * 3 + 1) - B.order_of_key(pos[i] * 3 + 1);
B.erase(i * 3 + 1);
B.insert(pos[i]*3);
}
}
}
// for (auto i : spos) {
// std::cerr << i << ' ';
// }
// std::cerr << '\n';
// for (auto i : rpos) {
// // std::cerr << i << ' ';
// }
// std::cerr << '\n';
// for (auto i : pos) {
// std::cerr << i << ' ';
// }
delete[] qm;
delete[] qp;
return count;
}