| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1311203 | dimitri.shengelia | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
map <int, vector <int>> mp;
int count_swaps ( vector <int> a ) {
int n = a.size();
ordered_set <int> st;
vector <bool> visited( n, false );
int answer = 0;
for ( int i = 0; i < n; i++ ) {
mp[a[i]].push_back( i );
}
for ( int i = 0; i < n; i++ ) {
if ( visited[i] == true ) {
continue;
}
int j = i;
int x = a[i], y = -1 * a[i];
int z = mp[y][0];
visited[z] = true;
auto it = st.lower_bound( z );
if ( it == st.end() ) {
z -= st.size();
} else {
z -= st.order_of_key( *it );
}
it = st.lower_bound( i );
if ( it == st.end() ) {
j -= st.size();
} else {
j -= st.order_of_key( *it );
}
answer += z - j - 1;
if ( x > 0 ) {
answer++;
}
st.insert( i );
st.insert( z );
mp[x].erase( mp[x].begin() );
mp[y].erase( mp[y].begin() );
}
return answer;
}
/*
//#include "shoes.h"
#include <cstdio>
#include <cassert>
using namespace std;
int main() {
int n;
assert(1 == scanf("%d", &n));
vector<int> S(2 * n);
for (int i = 0; i < 2 * n; i++)
assert(1 == scanf("%d", &S[i]));
fclose(stdin);
long long result = count_swaps(S);
printf("%lld\n", result);
fclose(stdout);
return 0;
}*/