Cod sursa(job #30620)

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


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

void add(long long nod,long long st,long long dr,long long a)
{  long 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 long query(long long nod,long long st,long long dr,long long a){
long 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 long SEARCH(long long k){
long 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 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 long i;
    FILE *g;
    g=fopen("farfurii.out","w");
    for(i=1;i<=N;i++)
       fprintf(g,"%lld ",sol[i]);
    fclose(g);
} 

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