Cod sursa(job #30614)

Utilizator t30Rosu Teodor t30 Data 14 martie 2007 19:02:14
Problema Farfurii Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<stdio.h>
long n,N,x,t[300100],sol[100100];


void READ(){
	FILE *f;
	f=fopen("farfurii.in","r");
	fscanf(f,"%ld %ld",&n,&x);
	fclose(f);
}

void add(long nod,long st,long dr,long a)
{  long m;
   if(st==dr) t[nod]=1;
   else { m=(st+dr)>>1;
	 if(a<=m)  add(nod*2,st,m,a);
	 else add(2*nod+1,m+1,dr,a);
	 t[nod]=t[nod]+1;
   }
}

long query(long nod,long st,long dr,long a){
long m;
   if(st==dr) return st;
   else { m=(st+dr)>>1;
	  if(a<=dr-m-t[2*nod+1]) return query(2*nod+1,m+1,dr,a);
	  else return query(2*nod,st,m,a-(dr-m-t[2*nod+1]));
	}
}



long SEARCH(long k){
long p,i;
   for(p=1;p<=n;p<<=1);
   for(i=0;p;p>>=1)
      if(i<=n && (i+p)*(i+p+1)/2<=k ) i+=p;
return i;
}

void SOLVE()
{  long k,q;
   N=n;
   while(n){
      k=SEARCH(x);
      x-=k;
      q=query(1,1,N,k+1);
      sol[ q ]=n;
      add(1,1,N,q);
      n--;
   }
}


void PRINT(){
long i;
    FILE *g;
    g=fopen("farfurii.out","w");
    for(i=1;i<=N;i++)
       fprintf(g,"%d ",sol[i]);
    fclose(g);
} 

int main()
{
READ();
SOLVE();
PRINT();
return 0;
}