Cod sursa(job #568271)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 30 martie 2011 23:46:21
Problema Farfurii Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<fstream>
#include<iostream>
using namespace std;

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

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 int& n, int& inv, const int& ramas)
{
	int left=1,right=n,mij,sol,inversari;

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

int main()
{
	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);
		out<<rez<<" ";
		used[rez]=1;
	}
	for(int i=1;i<=n;i++)
		if(!used[i])
		{
			out<<i;
			break;
		}
	out<<endl;
	in.close();
	out.close();
}