Submission #1067868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067868		Gromp15	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	237 ms	24664 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#define ll long long
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

struct fenwick {
	int n; vector<int> bit;
	fenwick(int a) : n(a), bit(a+1) {}
	void update(int pos, int x) {
		pos++;
		for (int i = pos; i <= n; i += i&-i) bit[i] += x;
	}
	int sum(int pos) {
		int res = 0;
		while (pos) res += bit[pos], pos -= pos&-pos;
		return res;
	}
	int query(int l, int r) {
		return sum(r+1) - sum(l);
	}
};

long long count_swaps(std::vector<int> s) {
	int n = sz(s);
	vector<bool> vis(n);
	ll ans = 0;
	map<int, vector<int>> mp;
	for (int i = 0; i < n; i++) {
		mp[s[i]].emplace_back(i);
	}
	for (auto &[x, y] : mp) reverse(all(y));
	fenwick fw(n);
	for (int i = 0; i < n; i++) if (!vis[i]) {
		int pos = mp[-s[i]].back();
		mp[s[i]].pop_back();
		mp[-s[i]].pop_back();
		assert(pos >= i);
		ans += pos - i - (s[i] < 0) - fw.query(i, pos);
		fw.update(pos, 1);
		vis[i] = 1, vis[pos] = 1;
	}
	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