Submission #350649

#	Time	Username	Problem	Language	Result	Execution time	Memory
350649		phenius	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	55 ms	5104 KiB

shoes

#include "shoes.h"


using namespace std;
#define MAXN 100000

int a[2 * MAXN];
int shoes[2 * MAXN];
int index[2 * MAXN + 1];
int cnt[MAXN], cntl[MAXN];
int N;

void clear_array(int *ar, int n) {
	for (register int i = 0; i < n; i++)
		ar[i] = 0;
}

void copy_arr(int *a1, vector <int> a2, int n) {
	for (int i = 0; i < n; i++)
		a1[i] = a2[i];
}

class BIT
{
	int count(int right)
	{
		register int cnt = 0;
		for (; right >= 0; right = (right & (right + 1)) - 1)
		{
			cnt += a[right];
		}
		return cnt;
	}

public:
	BIT()
	{
		clear_array(a, 2 * N);
	}

	int count(int left, int right)
	{
		return count(right) - count(left - 1);
	}

	void insert(int index)
	{
		for (; index < 2 * N; index = index | (index + 1))
		{
			a[index]++;
		}
	}
};

void create_index()
{
	clear_array(index, 2 * N + 1);
	for (register int i = 0; i < 2 * N; i++)
	{
		index[shoes[i] + N] = i;
	}
}

void convert() {
	clear_array(cnt, N);

	for (int i = 0; i < 2 * N; i++)
		if (shoes[i] > 0)
			cnt[shoes[i] - 1]++;

	for (int i = 1; i < N; i++) {
		cnt[i] += cnt[i - 1];
		cntl[i] = cnt[i];
	}
	cntl[0] = cnt[0];

	for (int i = 0; i < 2 * N; i++)
		if (shoes[i] > 0)
			shoes[i] = (--cntl[shoes[i] - 1]) + 1;
		else
			shoes[i] = -((--cnt[-shoes[i] - 1]) + 1);
}

long long count_swaps(vector<int> S)
{
	N = S.size() / 2;
	copy_arr(shoes, S, 2 * N);

	convert();
	create_index();
	BIT tree = BIT();

	long long ans = 0;

	for (int i = 0; i < 2 * N; i++)
	{
		if (shoes[i] != 0)
		{
			int pos = index[-shoes[i] + N];
			ans += pos - i - tree.count(i, pos) - (shoes[i] < 0 ? 1 : 0);
			shoes[pos] = 0;
			tree.insert(pos);
		}
	}
	return ans;
}

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