Submission #170618

#	Time	Username	Problem	Language	Result	Execution time	Memory
170618		nobik	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	753 ms	148188 KiB

shoes

#include "shoes.h"

#include <bits/stdc++.h>
using namespace std;

struct FenwichTree {
	int n;
	vector<int> f;

	FenwichTree(int n): n(n), f(n + 1) {}

	void Modify(int pos, int value) {
		for (int i = pos + 1; i <= n; i += i & -i) {
			f[i] += value;
		}
	}

	int Get(int pos) {
		int result = 0;
		for (int i = pos + 1; i > 0; i -= i & -i) {
			result += f[i];
		}

		return result;
	}
};

vector<int> GetShoePairs(const vector<int>& s) {
	int n = static_cast<int>(s.size());

	vector<int> shoe_pair(n);
	map<int, queue<int>> position;

	for (int i = 0; i < n; ++i) {
		int shoe = s[i];
		if (!position[-shoe].empty()) {
			int pos = position[-shoe].front();
			shoe_pair[pos] = i;
			shoe_pair[i] = pos;
			position[-shoe].pop();
			continue;
		}

		position[shoe].push(i);
	}

	return shoe_pair;
}

long long count_swaps(std::vector<int> s) {
	int n = static_cast<int>(s.size());
	vector<int> shoe_pair = GetShoePairs(s);
	vector<int> used(n);

	FenwichTree tree(n);
	for (int i = 0; i < n; ++i) 
		tree.Modify(i, +1);

	long long result = 0;
	for (int i = 0; i < n; ++i) {
		if (used[i])
			continue;

		int pr = shoe_pair[i];
		int actual_pos = tree.Get(pr) - 1;

		if (s[i] < 0)
			result += actual_pos - 1;
		else
			result += actual_pos;

		used[i] = used[pr] = 1;
		tree.Modify(i, -1);
		tree.Modify(pr, -1);
	}

	return result;
}

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