Cod sursa(job #2715278)

Utilizator Iulia25Hosu Iulia Iulia25 Data 3 martie 2021 14:43:31
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>

using namespace std;

ifstream cin ("farfurii.in");
ofstream cout ("farfurii.out");

const int N = 1e5 + 5;

long long k;
int n, start = 1;
int a[4 * N];

void Update(int nod)	{
	a[nod] = a[nod + nod] + a[nod + nod + 1];
	if (nod > 1)
		Update(nod / 2);
}

int Query(int x)	{
	int nod = 1, aux = 0;
	while (nod < start)	{
		if (a[nod + nod] + aux < x)	{
			aux += a[nod + nod];
			nod += nod + 1;
		} else	{
			nod += nod;
		}
	}
	return nod - start + 1;
}

int main()  {
	cin >> n >> k;
	while (start < n)
		start <<= 1;
	for (int i = 1; i <= n; ++i)	{
		a[i + start - 1] = 1;
		Update((i + start - 1) / 2);
	}
	int poz;
	for (int i = 1; i <= n; ++i)	{
		long long urm = (long long)(n - i) * (long long)(n - i - 1) / 2LL;
		if (urm >= k)	{
			poz = 1;
		} else	{
			poz = k - urm + 1;
		}
		k -= poz - 1;
		int x = Query(poz);
		cout << x << ' ';
		a[x + start - 1] = 0;
		Update((x + start - 1) / 2);
	}
	return 0;
}