Submission #563167

#	Time	Username	Problem	Language	Result	Execution time	Memory
563167		imtiyazrasool92	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	354 ms	25932 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> A) {
	const int N = (int)A.size();

	map<int, vector<int>> c_neg, c_pos;
	for (int i = N - 1; i >= 0; i--)
		if (A[i] < 0)
			c_neg[A[i]].push_back(i);
		else
			c_pos[A[i]].push_back(i);

	vector<bool> visited(N);
	fenwick<int> add(N);

	long long steps = 0;
	int previous = 0;
	for (int index = 0, pos = 0; index < N;) {
		if (visited[index]) {
			index++;
			continue;
		}

		if (pos % 2 == 0) {
			if (A[index] > 0) {
				int it = c_neg[-A[index]].back();
				c_neg[-A[index]].pop_back();
				c_pos[A[index]].pop_back();

				steps += (it + add.get(it)) - pos;

				add.update(index, 1);
				add.update(it, -1);

				previous = abs(A[index]);

				visited[it] = true;
				index++;
				pos += 2;
			} else {
				c_neg[A[index]].pop_back();
				previous = abs(A[index]);
				index++;
				pos++;
			}
		} else {
			if (A[index] != previous) {
				int it = c_pos[previous].back();
				c_pos[previous].pop_back();
				visited[it] = true;

				steps += (it + add.get(it)) - pos;

				add.update(index, 1);
				add.update(it, -1);
				pos++;
			} else {
				c_pos[A[index]].pop_back();
				index++;
				pos++;
			}
		}
	}

	return steps;
}

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