Cod sursa(job #1099274)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 5 februarie 2014 18:35:16
Problema Order Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<cstdio>

using namespace std;

const int NMAX = 30000+5;

int N,K,L,R;
int AInt[2*NMAX];

void Build(int lo,int hi,int node)
{
    if(lo==hi)
    {
        AInt[node] = 1;
        return;
    }

    int mi = (lo + hi)/2;

    Build(lo,mi,2*node);
    Build(mi+1,hi,2*node+1);

    AInt[node] = AInt[2*node] + AInt[2*node+1];
}

int Query(int lo,int hi,int node,int x)
{
    if(lo==hi)
        return lo;

    int mi = (lo+hi)/2;

    if(x<=AInt[2*node]) return Query(lo,mi,2*node,x);
    return Query(mi+1,hi,2*node+1,x-AInt[2*node]);
}

void Update(int lo,int hi,int node,int x)
{
    if(lo==hi)
    {
        AInt[node]=0;
        return;
    }

    int mi = (lo+hi)/2;

    if(x<=mi) Update(lo,mi,2*node,x);
    else Update(mi+1,hi,2*node+1,x);

    AInt[node] = AInt[2*node] + AInt[2*node+1];
}

int main()
{
    int i,k,m,x;

    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);

    scanf("%d",&N);

    Build(1,N,1);

    for(i=1,k=2; i<=N; i++)
    {
        m = AInt[1];
        k = (k + i-1)%m;
        if(!k) k=m;
        x = Query(1,N,1,k);
        Update(1,N,1,x);
        printf("%d ",x);
    }
    return 0;
}