Cod sursa(job #568288)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 31 martie 2011 00:06:48
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<fstream>
#include<iostream>
using namespace std;

const int NMAX=100005;
int aib[NMAX],used[NMAX];

inline int lsb(int x)
{
	return x&(-x);
}

void update(int poz, int val, int n)
{
	while(poz<=n)
	{
		aib[poz]+=val;
		poz+=lsb(poz);
	}
}

int query(int poz, int n)
{
	int sum=0;
	
	while(poz>0)
	{
		sum+=aib[poz];
		poz-=lsb(poz);
	}
	return sum;
}

int search(const long long int& n, long long int& inv, const int& ramas)
{
	int left=1,right=n,mij,sol=1;
	long long int inversari;

	long long int sum=(long long int) ramas*(ramas-1);
	sum/=2;
	inversari=inv;
	if(inversari<sum)
		inversari=0;
	else
		inversari-=sum;
	while(left<=right)
	{
		mij=left+(right-left)/2;
		int indice=query(mij,n);
		if(indice>inversari+1)
			right=mij-1;
		else if(indice<inversari+1)
			left=mij+1;
		else
		{
			if(!used[mij])
			{
				sol=mij;
				break;
			}
			else
				right=mij-1;
		}
	}
	update(sol,-1,n);
	inv-=inversari;
	return sol;
}

int main()
{
	long long int n,k;

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

	in>>n>>k;
	for(int i=1;i<=n;i++)
		update(i,1,n);
	for(int i=1;i<=n-1;i++)
	{
		int rez=search(n,k,n-i);
		used[rez]=1;
		out<<rez<<" ";
	}
	for(int i=1;i<=n;i++)
		if(!used[i])
		{
			out<<i;
			break;
		}
	out<<endl;
	in.close();
	out.close();
}