IOI 2014 day 2

gondola.cpp

#include "gondola.h"

#include <bits/stdc++.h>

using namespace std;

void fix(int n, int inputSeq[])
{
	auto mn = min_element(inputSeq, inputSeq + n);

	if (*mn > n)
		return;

	rotate(inputSeq, inputSeq + (mn - inputSeq - *mn + 1 + n) % n, inputSeq + n);
}

int valid(int n, int inputSeq[])
{
	fix(n, inputSeq);

	for (int i = 0; i < n; ++i)
		if (inputSeq[i] <= n && inputSeq[i] != i + 1)
			return 0;

	sort(inputSeq, inputSeq + n);
	if (unique(inputSeq, inputSeq + n) != inputSeq + n)
		return 0;

	return 1;
}

//----------------------

pair<int, int> sorted[100100];

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	int m = 0, i;
	int curr, nxt = n + 1;

	fix(n, gondolaSeq);

	for (i = 0; i < n; ++i)
		sorted[i] = make_pair(gondolaSeq[i], i + 1);

	sort(sorted, sorted + n);

	for (i = 0; i < n && sorted[i].first <= n; ++i);

	for (; i < n; ++i)
	{
		curr = sorted[i].second;

		while (nxt <= sorted[i].first)
		{
			replacementSeq[m++] = curr;
			curr = nxt++;
		}
	}

	return m;
}

//----------------------

const long long MOD = 1000000009;

long long fpow(long long a, long long b)
{
	if (a == 1 || b == 0)
		return 1;
	if (a == 0 || b == 1)
		return a;

	long long res = fpow(a * a % MOD, b / 2);

	if (b % 2)
	{
		res *= a;
		res %= MOD;
	}

	return res;
}

int countReplacement(int n, int inputSeq[])
{
	if (!valid(n, inputSeq))
		return 0;

	int i;
	int prev = n;
	long long m = 1;

	sort(inputSeq, inputSeq + n);

	if (inputSeq[0] > n)
		m = n;

	for (i = 0; i < n && inputSeq[i] <= n; ++i);

	for (; i < n; ++i)
	{
		m *= fpow(n - i, inputSeq[i] - prev - 1);
		m %= MOD;
		prev = inputSeq[i];
	}

	return m;
}