Submission #1316965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316965		khfares	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	291 ms	34836 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll sum(vector<ll>& fenw, ll x) {
	ll res = 0;
	while (x > 0) {
		res += fenw[x];
		x -= (x&(-x));
	}
	return res;
}
void add(vector<ll>& fenw, ll x, ll k) {
	while (x < fenw.size()) {
		fenw[x] += k;
		x += (x&(-x));
	}
}

long long count_swaps(std::vector<int> s) {
	ll n = s.size();
	map<ll, pair<vector<ll>, ll>> mp;
	for (ll i = 0; i < n; i++) {
		mp[s[i]].first.push_back(i);
		mp[s[i]].second = 0;
	}

	vector<ll> fenw(n+1, 0);
	for (ll i = 1; i < n+1; i++) {
		add(fenw, i, 1);
	}
	ll ans = 0;
	set<ll> st;
	for (ll i = 0; i < n; i++) {
		if (st.count(i)) continue;


		ll i2 = mp[-s[i]].first[mp[-s[i]].second];

		ans += sum(fenw, i2)-sum(fenw, i+1);

		if (s[i] > 0) ans++;

		add(fenw, i+1, -1);
		add(fenw, i2+1, -1);
		mp[-s[i]].second++;
		mp[s[i]].second++;
		st.insert(i);
		st.insert(i2);
	}
	return ans;
}

//int main() {
//	cout << count_swaps({-2, 2, 2, -2, -2, 2}) << endl;
//}

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