Cod sursa(job #1366233)

Utilizator delia_99Delia Draghici delia_99 Data 28 februarie 2015 21:15:18
Problema Order Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <cstdio>

using namespace std;
int n,i,A[60010],p,ind,pos,nodr;

void upd(int nod,int a,int b,int st,int dr)
{
    int mij;
    if(a<=st && dr<=b)
    {
        ++A[nod];
        return;
    }
    mij=st+(dr-st)/2;
    if(a<=mij)  upd(2*nod,a,b,st,mij);
    else upd(2*nod+1,a,b,mij+1,dr);
    if(2*nod+1<2*n+10)
        A[nod]=A[2*nod]+A[2*nod+1];
    else if(2*nod<2*n+10)
        A[nod]=A[2*nod];

}

void find(int nod,int p,int st,int dr)
{
    int mij;
    if(st==dr)
    {
        pos=st;
        nodr=nod;
        return;
    }
    mij=st+(dr-st)/2;
    if(p<=A[2*nod])  find(2*nod,p,st,mij);
    else find(2*nod+1,p-A[2*nod],mij+1,dr);
}

void remove(int nod)
{
    --A[nod];
    if(nod==1)
        return;
    else remove(nod/2);
}

int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d ",&n);
    for(i=1; i<=n; ++i)
        upd(1,i,i,1,n);
    ind=n;
    p=2;
    for(i=1; i<=n; ++i)
    {
        --ind;
        find(1,p,1,n);
        printf("%d ",pos);
        remove(nodr);
        p+=i;
        if(ind!=0)
        {
            p%=ind;
            if(p==0)
                p=ind;
        }
    }
    return 0;
}