Cod sursa(job #1847083)

Utilizator andysoloAndrei Solo andysolo Data 14 ianuarie 2017 11:57:00
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#define lb(x) x&(-x)
#define NMAX 30000
#include <cstdio>
using namespace std;

int N,AiB[NMAX+5],temp[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;
        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);
        temp[i]=1;
    }

    int c=1,cN=N;
    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);
            temp[d]=0;
            c=d;
        }
        else
        {
            int xp=(delta+mod)%tot;
                if(xp==0)xp=tot;
            int d2=bin(xp);
            printf("%d ",d2);
            setAiB(d2,-1);
            temp[d2]=0;
            c=d2;
        }
    }

    return 0;
}