Cod sursa(job #1846988)

Utilizator andysoloAndrei Solo andysolo Data 14 ianuarie 2017 11:03:31
Problema Order Scor 0
Compilator cpp Status done
Runda aib-uuri_cex Marime 1.26 kb
#define lb(x) x&(-x)
#define NMAX 30000
#include <cstdio>
using namespace std;

int N,AiB[NMAX+5];

void setAiB(int,int);
int getAiB(int);

int bin(int x)
{
    int f=1,s=N;
    int m=0;

    while(f<=s){

    m=(f+s)>>1;
    int sum=getAiB(m);

    if(sum==x)
        return m;
    else if(sum<x)
        f=m+1;
    else s=m-1;
    }

    return -537;
}

void setAiB(int j,int k)
{
    for(int i=j; i<=N; i+=lb(i))
        AiB[i]+=k;
}

int getAiB(int j)
{
    int p=0;
    for(int i=j; i>=1; i-=lb(i))
        p+=AiB[i];
    return p;
}

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

    scanf("%d",&N);

    for(int i=1; i<=N; i++)
        setAiB(i,1);

    int c=1;
    for(int i=1; i<=N; i++)
    {
        int delta=getAiB(c);
        int tot=getAiB(N);
        int mod=i%tot;
        if(mod==0)
            mod=tot;
        int d=bin(delta+mod);


        if(d!=-537)
        {
            printf("%d ",d);
            setAiB(d,-1);
            c=d;
        }
        else
        {
            int mod2=bin((delta+mod)%tot);
            int d2=bin(mod2);
            printf("%d ",d2);
            setAiB(d2,-1);
            c=d2;
        }
    }

    return 0;
}