Cod sursa(job #59488)

Utilizator crawlerPuni Andrei Paul crawler Data 9 mai 2007 15:24:01
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <stdio.h>

int n, v[60100], poz = 1, nr, N;
char o[60100];

void update(int x,int val)
 {
  o[x] += val; 
  for(;x<=N;x+=x^(x-1) & x)
   v[x] += val;
 }
 
int query(int x)
 {
  int r = 0;
  for(;x;x-=x^(x-1) & x)
   r += v[x];
  return r;
 }

void search(int val)
 {
  int st = poz, dr = n<<1, mij, tmp, aux = query(poz);
  
  while(st<dr)
   {
    mij = (st+dr)/2;

    tmp = query(mij) - aux;
    
    if(tmp < val)
     st = mij + 1;
      else
    if(tmp > val)
     dr = mij;
      else
     st = dr = mij;
   }
  poz = mij;
  
  while(!o[poz])
   {
    --poz;
    if(!poz) poz = n;
   }
   
  if(poz>n)
   poz -= n;
 }

int main()
 {
  freopen("order.in","r",stdin);
  freopen("order.out","w",stdout);

  int i;

  scanf("%d", &n);
  nr = n;
  N = n<<1;

  for(i=1;i<=n;++i)
   update(i,1), update(i+n,1);

  for(i=1;i<=n;++i,--nr)
   {
    search(i%nr);
    printf("%d ",poz);
    update(poz,-1);
    update(poz+n,-1);
   }
   
  return 0;
 }