Cod sursa(job #826647)

Utilizator maritimCristian Lambru maritim Data 30 noiembrie 2012 23:45:10
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 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]);
}

inline int querry(int li,int ls,int poz,int pozVal)
{
    if(li == ls)
        return AINT[poz];

    if(pozVal > mij)
        return AINT[fs]+querry(mij+1,ls,fd,pozVal);
    else
        return querry(li,mij,fs,pozVal); 
}

void afisare(void)
{
    for(int i=1;i<=N<<1;i++)
        printf("%d ",AINT[i]);
    printf("\n");
}

int main()
{
    int a = 1;

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