Cod sursa(job #826649)

Utilizator maritimCristian Lambru maritim Data 30 noiembrie 2012 23:47:44
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<stdio.h>

FILE *f = fopen("order.in","r");
FILE *g = fopen("order.out","w");

#define MaxAINT 65100
#define mij ((li+ls)>>1)
#define fs (poz<<1)
#define fd ((poz<<1)+1)

int N;
int AINT[MaxAINT];

void citire(void)
{
    fscanf(f,"%d",&N);
}

inline void build(int li,int ls,int poz)
{
    if(li == ls)
    {
        AINT[poz] = 1;
        return ;
    }

    build(li,mij,fs);
    build(mij+1,ls,fd);

    AINT[poz] = AINT[fs]+AINT[fd];
}

inline void update(int li,int ls,int poz,int pozVal)
{
    if(li == ls)
    {
        AINT[poz] = 0;
        return ;
    }

    if(li <= pozVal && pozVal <= mij)
        update(li,mij,fs,pozVal);
    else
        update(mij+1,ls,fd,pozVal);

   AINT[poz] = AINT[fs]+AINT[fd]; 
}

inline int pozSearch(int li,int ls,int poz,int pozS)
{
    if(li == ls)
        return li;

    if(AINT[fs] >= pozS)
        return pozSearch(li,mij,fs,pozS);
    else
        return pozSearch(mij+1,ls,fd,pozS-AINT[fs]);
}

int main()
{
    int a = 2,poz;

    citire();
    build(1,N,1);
    for(int i=1;i<=N;i++)
    {
        a = (a-1+i)%AINT[1];
        if(!a)
            a = AINT[1];
        poz = pozSearch(1,N,1,a);
        update(1,N,1,poz);
        fprintf(g,"%d ",poz);
    }
}