Submission #563112

#	Time	Username	Problem	Language	Result	Execution time	Memory
563112		imtiyazrasool92	Arranging Shoes (IOI19_shoes)	C++17	25 / 100	293 ms	26264 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();

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

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

	vector<bool> visited(N);

	long long 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) {
				int it = closest_negative.back();
				steps += (it + add.get(it)) - i;
				previous = abs(s[it]);
				visited[it] = true;
				add.update(index, 1);
				add.update(it, -1);
				closest_negative.pop_back();
			} else {
				previous = abs(s[index]);
				closest_negative.pop_back();
				index++;
			}
			continue;
		}

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

	}

	return steps;
}

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