Cod sursa(job #34345)

Utilizator stef2nStefan Istrate stef2n Data 20 martie 2007 17:44:45
Problema Farfurii Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <stdio.h>

#define infile "farfurii.in"
#define outfile "farfurii.out"
#define DIMMAX 262200

FILE *fin,*fout;
int count[DIMMAX];

int binary_search(int n, int li, int ls, int &k)
  {
   if(li==ls)
     return li;
   int mij=(li+ls)/2;
   int nrinv=k-mij+1;
   if(nrinv>(n-1)*(n-2)/2)
     return binary_search(n,mij+1,ls,k);
   else
     return binary_search(n,li,mij,k);
  }

void build(int n, int li, int ls)
  {
   if(li==ls)
     {
      count[n]=1;
      return;
     }
   build(2*n,li,(li+ls)/2);
   build(2*n+1,(li+ls)/2+1,ls);
   count[n]=count[2*n]+count[2*n+1];
  }

int delete_first(int n, int li, int ls, int first)
  {
   int aux;
   if(li==ls)
     {
      count[n]=0;
      return li;
     }
   if(count[2*n]>=first)
     aux=delete_first(2*n,li,(li+ls)/2,first);
   else
     aux=delete_first(2*n+1,(li+ls)/2+1,ls,first-count[2*n]);
   count[n]=count[2*n]+count[2*n+1];
   return aux;
  }

void solve(int n, int k)
  {
   int i,first;
   build(1,1,n);
   for(i=0;i<n;i++)
      {
       first=binary_search(n-i,1,n-i,k);
       fprintf(fout,"%d ",delete_first(1,1,n,first));
       k=k-first+1;
      }
  }


int main()
{
int n,k;
fin=fopen(infile,"r");
fscanf(fin,"%d %d",&n,&k);
fclose(fin);
fout=fopen(outfile,"w");
solve(n,k);
fclose(fout);
return 0;
}