Cod sursa(job #235341)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 23 decembrie 2008 14:25:22
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<stdio.h>
#include<string.h>
FILE*fin=fopen("order.in","r");
FILE*fout=fopen("order.out","w");
#define maxn 40005
int n,t[2*maxn+1];
int find(int nod,int st,int dr,int k)
{
  int mij;
  if(st==dr) return st;
  else
  {
    mij=(st+dr)/2;
    if(k<=t[nod*2]) return find(nod*2,st,mij,k);
    else return find(nod*2+1,mij+1,dr,k-t[nod*2]);
  }
}
void update(int nod,int st,int dr,int a,int b)
{
  int mij;
  if(st==dr) t[nod]=b;
  else
  {
    mij=(st+dr)/2;
    if(a<=mij) update(nod*2,st,mij,a,b);
    else update(nod*2+1,mij+1,dr,a,b);
    t[nod]=t[nod*2]+t[nod*2+1];
  }
}
int main()
{
  int i,w,d,nn,e;
  fscanf(fin,"%d",&n);
  memset(t,0,sizeof(t));
  for(i=1;i<=n;i++)
    update(1,1,n,i,1);
  nn=n;
  i=1;w=1;
  while(nn)
  {
    d=(w+i)%nn;
    if(d==0) d=nn;
    e=find(1,1,n,d);
    fprintf(fout,"%d ",e);
    update(1,1,n,e,0);
    w=d-1;
    if(w==0) w=nn-1;
    nn--;
    i++;
  }
  fclose(fin);
  fclose(fout);
  return 0;
}