Submission #1019846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019846		eldorbek_008	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	697 ms	159792 KiB

shoes

#include "shoes.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

using namespace __gnu_pbds;
using namespace std;

// ordered_set
template<class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

long long count_swaps(vector<int> s) {
  int n = s.size();
  map<int, deque<int>> id;
  Tree<pair<int, int>> t;
  for (int i = 0; i < n; i++) {
  	id[s[i]].push_back(i);
  	t.insert(make_pair(i, s[i]));
  }
  long long ans = 0;
  for (int i = 0; i < n / 2; i++) {
  	auto j = t.find_by_order(0);
  	int p = -((*j).second);
  	int d = t.order_of_key(make_pair(id[p][0], p));
  	ans += d - (p > 0 ? 1 : 0);
  	t.erase(j);
  	t.erase(t.find(make_pair(id[p][0], p)));
  	id[p].pop_front();
  	id[-p].pop_front();
  }
  return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15