Submission #145385

#	Time	Username	Problem	Language	Result	Execution time	Memory
145385		Eae02	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	678 ms	148040 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using ll = long long;
using namespace std;

map<int, deque<int>> positions;

inline int LSB(int x)
{
	return x & (-x);
}

class FenwickTree
{
public:
	FenwickTree(size_t size) : V(size + 1, 0) { }
	
	//Prefix sum of the first n items (nth not included)
	int PrefixSum(int n)
	{
		int sum = 0;
		for (; n; n -= LSB(n))
			sum += V[n];
		return sum;
	}
	
	void Adjust(int i, int delta)
	{
		i++;
		for (; i < V.size(); i += LSB(i))
			V[i] += delta;
	}
	
private:
	std::vector<int> V;
};

ll count_swaps(vector<int> s) {
	FenwickTree removed(s.size());
	
	for (int i = 0; i < (int)s.size(); i++) {
		positions[s[i]].push_back(i);
	}
	
	vector<bool> done(s.size(), false);
	
	ll swaps = 0;
	for (int i = 0; i < (int)s.size(); i++) {
		if (done[i])
			continue;
		
		int v = s[i];
		
		deque<int>& posNeg = positions.at(-v);
		int negIdx = posNeg.front();
		posNeg.pop_front();
		positions.at(v).pop_front();
		
		swaps += negIdx - (removed.PrefixSum(negIdx) - removed.PrefixSum(i)) - i;
		
		removed.Adjust(negIdx, 1);
		done[negIdx] = true;
		
		if (v < 0)
			swaps--;
	}
	
	return swaps;
}

Compilation message (stderr)

shoes.cpp: In member function 'void FenwickTree::Adjust(int, int)':
shoes.cpp:31:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (; i < V.size(); i += LSB(i))
          ~~^~~~~~~~~~

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