Submission #563108

#	Time	Username	Problem	Language	Result	Execution time	Memory
563108		imtiyazrasool92	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1048 ms	36700 KiB

shoes

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

// 0 base index
template <typename T>
class fenwick {
public:
	vector<T> fenw;
	int n;
	fenwick(int _n) : n(_n) {
		fenw.resize(n);
	}
	// index,value
	void update(int x, T v) {
		while (x < n) {
			fenw[x] += v;
			x |= (x + 1);
		}
	}
	// prefix sum till x
	T get(int x) {
		T v{};
		while (x >= 0) {
			v += fenw[x];
			x = (x & (x + 1)) - 1;
		}
		return v;
	}
	T get_range(int l, int r) {
		return get(r) - (l > 0 ? get(l - 1) : 0);
	}
};


long long count_swaps(std::vector<int> s) {
	const int N = (int)s.size();

	multiset<int> closest_negative;
	for (int i = N - 1; i >= 0; i--)
		if (s[i] < 0) {
			closest_negative.insert(i);
		}

	map<int, multiset<int>> closest_positive;
	for (int i = N - 1; i >= 0; i--)
		closest_positive[s[i]].insert(i);

	vector<bool> visited(N);

	int steps = 0;
	int previous = -1;

	fenwick<int> add(N);

	for (int i = 0, index = 0; i < N; i++) {
		if (visited[index]) {
			index++;
			continue;
		}

		if (i % 2 == 0) {
			if (s[index] > 0) {
				auto it = closest_negative.begin();
				steps += (*it + add.get(*it)) - i;
				previous = abs(s[*it]);
				visited[*it] = true;
				add.update(index, 1);
				add.update(*it, -1);
				closest_negative.erase(it);
			} else {
				previous = abs(s[index]);
				closest_negative.erase(closest_negative.find(index));
				index++;
			}
			continue;
		}

		if (s[index] != previous) {
			auto it = closest_positive[previous].begin();
			steps += (*it + add.get(*it)) - i;
			visited[*it] = true;
			add.update(index, 1);
			add.update(*it, -1);
			closest_positive[previous].erase(it);
		} else {
			closest_positive[previous].erase(closest_positive[previous].begin());
			index++;
		}

	}

	return steps;
}

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