| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1285740 | dssfsuper2 | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include "shoes.h"
#include "grader.cpp"
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
using pii=pair<int, int>;
#define ordered_set tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>
long long count_swaps(vector<int> s) {
ordered_set osef;
int res = 0;
vector<set<int>> vse(200003);
for(int i = 0;i<s.size();i++){
osef.insert({i, s[i]});
vse[s[i]+100001].insert(i);
}
while(!osef.empty()){
auto top = *(osef.begin());
osef.erase(osef.begin());
vse[top.second+100001].erase(top.first);
auto fir=*(vse[-top.second+100001].begin());
vse[-top.second+100001].erase(vse[-top.second+100001].begin());
auto dist = osef.order_of_key({fir, -top.second});
res+=dist;
if(top.second>0)res++;
osef.erase({fir, -top.second});
}
return res;
}
