Cod sursa(job #575699)

Utilizator mihai995mihai995 mihai995 Data 8 aprilie 2011 17:38:59
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
using namespace std;

const int N=100002;
int v[3*N],a[N],n,P,val;

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

inline void update(int poz,int st,int dr,int x,int val)
{
	if (st==dr)
	{
		v[poz]=val;
		return;
	}
	int m=(st+dr)>>1;
	if (x<=m)
		update(poz<<1,st,m,x,val);
	else
		update((poz<<1)+1,m+1,dr,x,val);
	v[poz]=v[poz<<1]+v[(poz<<1)+1];
}

inline void query(int poz,int st,int dr)
{
	if (v[poz]<=val)
	{
		val-=v[poz];
		if (P<dr)
			P=dr;
		return;
	}
	if (st==dr)
		return;
	int m=(st+dr)>>1;
	if (v[poz<<1]>val)
	{
		query(poz<<1,st,m);
		return;
	}
	val-=v[poz<<1];
	if (P<m)
		P=m;
	query((poz<<1)+1,m+1,dr);
}

inline int greedy(int x)
{
	P=0;
	val=x-1;
	query(1,1,n);P++;
	update(1,1,n,P,0);
	return P;
}

int main()
{
	int i;
	long long k;
	in>>n>>k;
	for (i=n;i;i--)
	{
		a[i]=n-i;
		if (k<n-i)
			a[i]=k;
		k-=a[i];
		update(1,1,n,i,1);
	}
	for (i=1;i<=n;i++)
		out<<greedy(a[i]+1)<<" ";
	out<<"\n";
	return 0;
}