Submission #955072

#	Time	Username	Problem	Language	Result	Execution time	Memory
955072		Macker	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	482 ms	47184 KiB

shoes

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

using namespace __gnu_pbds;

using namespace std;

typedef long long ll;
typedef long double ld;
#define int ll
typedef pair<int, int> pii;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define FOR(i, n) for (int i = 0; i < n; i++)

typedef tree<
pair<int, pii>,
null_type,
less<pair<int, pii>>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

int count_swaps(vector<signed> s) {
	int n = s.size();
	map<int, int> m;
	vector<pii> v(n);
	FOR(i, n){
		v[i] = {s[i], m[s[i]]};
		m[s[i]]++;
	}
	ordered_set st;
	map<pii, int> pos;
	FOR(i, n){
		st.insert({i, v[i]});
		pos[v[i]] = i;
	}
	
	int res = 0;
	FOR(i, n / 2){
		pii cur = (*--st.end()).ss;
		pii ot = {-cur.ff, cur.ss};
		res += st.size() - st.order_of_key({pos[ot], ot}) - 2;
		if(cur.ff < 0) res++;
		st.erase(--st.end());
		st.erase({pos[ot], ot});
		/*
		for (auto &j : st) {
			cout << j.ff << " " << j.ss.ff << " " << j.ss.ss << "    ";	
		}
		cout << res << endl;
		*/
	}
	return res;
}

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