Submission #377013

#	Time	Username	Problem	Language	Result	Execution time	Memory
377013		sliviu	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	335 ms	274156 KiB

shoes

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll count_swaps(vector<int> v) {
	int n = v.size();
	ll ans = 0;
	vector<int> bit(n + 1);
	vector<queue<int>> Q(2 * n + 1);
	for (int i = 0; i < n; ++i)
		Q[n + v[i]].emplace(i + 1);
	auto update = [&](int pos, int val) {
		while (pos <= n) {
			bit[pos] += val;
			pos += pos & -pos;
		}
	};
	auto query = [&](int pos) {
		int ans = 0;
		while (pos) {
			ans += bit[pos];
			pos -= pos & -pos;
		}
		return ans;
	};
	for (int i = 1, j = 1; i <= n; ++i) {
		int cur = v[i - 1], cmp = -cur;
		if (!cur)
			continue;
		int top = Q[n + cmp].front();
		Q[n + cmp].pop(), Q[n + cur].pop();
		ans += (cur > 0) + top - j - 1 + query(top);
		update(i + 1, 1);
		update(top + 1, -1);
		v[top - 1] = 0, j += 2;
	}
	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