Cod sursa(job #169079)

Utilizator mike4problemsRadu Gabriel mike4problems Data 1 aprilie 2008 00:25:43
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include<fstream>
#include<iostream>
using namespace std;

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

#define N 100000

int a[N*5];
long long n,k,i,sum;
long long t=1;

void use(int,int,int);

int main()
{
	fin>>n>>k;
	for(i=1;i<=n;i++)
	{
		sum=max(t,k-(n-i)*(n-i-1)/2+1);
		if(sum>1) k-=sum-1;
		use(1,1,n);
	}
	fout<<'\n';
	return 0;
}

void use(int k,int i,int j)
{
	if(i==j)
	{
		sum-=!a[k];
		if(!sum) 
		{
			fout<<i<<' ';
			a[k]=1;
		}
		return;
	}
	int mij=(i+j)/2;
	if(sum>j-i+1-a[k])
		sum-=j-i+1-a[k];
	else
	{
		use(2*k,i,mij);
		if(sum) use(2*k+1,mij+1,j);
		a[k]=a[2*k]+a[2*k+1];
	}
}