| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 861422 | Unforgettablepl | 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.
/*
ID: samikgo1
TASK: wormhole
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
//#define f first
//#define s second
//#define x first
//#define y second
const int INF = 1e9;
const ll modulo = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define int ll
int arr[200001];
int64_t count_swaps(std::vector<int> s) {
int n = s.size();
for(int i=1;i<=n;i++)arr[i]=s[i-1];
set<pair<int,int>> pairLookup;
ordered_set currActive;
for(int i=1;i<=n;i++)pairLookup.emplace(arr[i],i);
for(int i=1;i<=n;i++)currActive.insert(i);
int ans = 0;
for(int i=0;i<n/2;i++){
auto curr_first = *currActive.find_by_order(0);
currActive.erase(currActive.find_by_order(0));
pairLookup.erase(make_pair(arr[curr_first],curr_first));
if(arr[curr_first]>0)ans++;
auto curr_second = pairLookup.lower_bound(make_pair(-arr[curr_first],0))->second;
pairLookup.erase(make_pair(arr[curr_second],curr_second));
ans+=currActive.order_of_key(curr_second);
currActive.erase(curr_second);
}
return ans;
}