Cod sursa(job #287537)

Utilizator FlorianFlorian Marcu Florian Data 24 martie 2009 22:30:18
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 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;
 }