Cod sursa(job #382582)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 13 ianuarie 2010 23:06:20
Problema Farfurii Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include<stdio.h>

int i,j,a[400100],t[600100],n,l,rez;
long long k;

void update(int i,int st,int dr,int p)
{ 
	if(st==dr) 
	{ 
		t[i]++;
		return ;
	}
	
	int mij=(st+dr)/2;
	
	if(p<=mij) update(i*2,st,mij,p);
	else update(i*2+1,mij+1,dr,p);
	
	t[i]=t[i*2]+t[i*2+1];
}

void Search(int i,int st,int dr,int a,int b)
{ 
	if(a<=st&&dr<=b) 
	{
		rez+=t[i];
		return ;
	}
	
	int mij=(st+dr)/2;
	
	if(a<=mij) Search(i*2,st,mij,a,b);
	if(b>mij) Search(i*2+1,mij+1,dr,a,b);
	
}

int cautbin(int st,int dr,int x)
{ 
	int l=(dr-1)*(dr-2)/2;
	while(st<=dr) 
	{ 
		int mij=(st+dr)/2;
		if(mij-1+l==x) return mij;
		else if(mij-1+l>x) dr=mij-1;
		else st=mij+1;
	}
	
	return 0;
	
}
 
int main()
{ 
	freopen("farfurii.in","r",stdin);
	freopen("farfurii.out","w",stdout);
	
	scanf("%d %lld",&n,&k);
    
	if(n==2&&k==1) { printf("2 1\n");
	                 fclose(stdin);
					 fclose(stdout);
					 return 0;
	               }
	
	int st=1,dr=n;
	long long mij=0;
	
	while(st<=dr) 
	{
		mij=(st+dr)/2;
		
		if((mij*(mij-1)/2>=k&&(mij-1)*(mij-2)/2<k)||mij-1==0) break;
		else if(mij*(mij-1)/2>=k&&(mij-1)*(mij-2)/2>=k) dr=mij-1;
		else st=mij+1;
	}
	
	l=mij;
	int l1=l;
	l--;
	for(i=1;i<=l1;++i) 
	{
		a[i]=cautbin(1,l+1,k);
		l--;
		k-=(a[i]-1);
		rez=0;
		Search(1,1,l1,1,a[i]);
		a[i]+=rez;
		update(1,1,l1,a[i]);
	}
	
	l1=n-l1;
	
	for(i=1;i<=l1;++i) printf("%d ",i);
	for(k=1;i<=n;++i,++k) printf("%d ",a[k]+l1);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}