Cod sursa(job #290182)

Utilizator flamecataCiobanu Alexandru-Catalin flamecata Data 27 martie 2009 16:39:59
Problema Order Scor 100
Compilator cpp Status done
Runda aa Marime 1.2 kb
#include<stdio.h>   
#define Nmax 100002   
#define common int m=(r+l)/2, fs=2*n, fd=2*n+1;   
int H[Nmax];   
int s, P;   
void build(int n, int l,int r)   
 {   
  H[n] = r-l+1;   
  if(r==l) return;   
  common;   
  build(fs,l,m);   
  build(fd,m+1,r);   
  
  H[n] = H[fs] + H[fd];   
 }   
void upd(int n, int l, int r, int x)   
 {   
  if(l>=r)   
   {   
    H[n]=0;   
    return;   
   }   
  common;   
  if(x<=m) upd(fs,l,m,x);   
  else upd(fd,m+1,r,x);   
  
  H[n] = H[fs] + H[fd];   
 }   
int query(int n, int l, int r, int x)   
 {   
  if(l>=r)   
   {   
    return r;   
   }   
  common;   
  if(s+H[fs] < x) { s+=H[fs]; return query(fd,m+1,r,x); }   
  else return query(fs,l,m,x);   
  
 }   
int main()   
 {   
  int n;   
  freopen("order.in","r",stdin);   
  freopen("order.out","w",stdout);   
  scanf("%d",&n);   
  int i,N=n;   
  build(1,1,n);   
  int k,poz=1, pas=1;   
  poz=2;   
  for(;n;--n)   
   {   
    poz += pas%H[1] - 1;   
    if(poz>H[1]) poz-=H[1];   
    if(poz==0) poz=H[1];   
    s=0;   
    k = query(1,1,N,poz);   
    upd(1,1,N,k);   
    printf("%d ",k);   
    ++pas;   
    s=0;   
   }   
  return 0;   
 }