| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 988282 | kachim2 | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}