Submission #350354

#	Time	Username	Problem	Language	Result	Execution time	Memory
350354		phenius	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1 ms	364 KiB

shoes

#include "shoes.h"

using namespace std;
#define MAXN 10001

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

void clear_array(int *ar, int n) {
	for (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 Fenwick
{
	int n;
	int count(int right)
	{
		int cnt = 0;
		for (; right >= 0; right = (right & (right + 1)) - 1)
		{
			cnt += a[right];
		}
		return cnt;
	}

public:
	Fenwick()
	{
		clear_array(a, N);
	}

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

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

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

long long count_adjacent()
{
	create_index();
	Fenwick f = Fenwick();
	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 - f.count(i, pos) - (shoes[i] < 0 ? 1 : 0);
			shoes[pos] = 0;
			f.put(pos);
		}
	}
	return ans;
}

void change(vector<int> v) {
	int cnt[N];
	clear_array(cnt, N);
	copy_arr(shoes, v, 2 * N);
	for (int i = 0; i < 2 * N; i++)
		if (v[i] > 0)
			cnt[v[i] - 1]++;

	for (int i = 1; i < N; i++)
		cnt[i] += cnt[i - 1];

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


long long count_swaps(vector<int> S)
{
	N = S.size() / 2;
	change(S);
	return count_adjacent();
}

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