Cod sursa(job #1653899)

Utilizator krityxAdrian Buzea krityx Data 16 martie 2016 17:58:31
Problema Farfurii Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb




#include <fstream>
#include <queue>
#define NMAX 100005

using namespace std;

long long sol[NMAX];

bool check(int n, int k)
{
	int i, j, nr = 0;
	for (i = 1; i <= n; i++)
	{
		for (j = i + 1; j <= n; j++)
		{
			if (sol[i] > sol[j])
			{
				nr++;
			}
		}
	}

	if (nr != k)
	{
		return false;
	}
	return true;
}

int main()
{
	long long N, K, V[NMAX], i, sum, max, pIndex, element;

	ifstream f("farfurii.in");
	f >> N >> K;
	f.close();

	i = 1;
	sum = 0;
	V[N] = 0;

	while (sum + i <= K)
	{
		sum += V[N - i] = i;
		i++;
	}
	max = i;
	pIndex = N - i;
	element = N;
	if (pIndex < 0)
	{
		pIndex++;
	}
	bool once = true;
	for (i = pIndex + 1; i <= N; i++)
	{
		if (V[i - 1] == K - sum)
		{
			sol[i] = element - 1;
			sol[pIndex] = element;
			element -= 2;
		}
		else
		{
			sol[i] = element--;
		}
	}

	element = 1;

	ofstream g("farfurii.out");
	long long startIndex = 1, endIndex = N;

	for (i = startIndex; i <= N; i++)
	{
		if (sol[i] == 0)
		{
			sol[i] = element++;
			//g << element++ << " ";
		}
		//else
		//{
		//	g << sol[i] << " ";
		//}
	}
	if (!check(N, K))
	{
		vector<int> test;
		test.resize(1);
		while (true)
		{

		}
	}
	else
	{
		for (i = 1; i <= N; i++)
		{
			g << sol[i] << " ";
		}
	}
	g.close();

	return 0;
}