Cod sursa(job #1369822)

Utilizator andreimdvMoldovan Andrei andreimdv Data 3 martie 2015 11:36:31
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
using namespace std;

ifstream fin("order.in");
ofstream fout("order.out");


int n,i,pos,ramaspos,aux,aib[30010];


void actualizare(int pos, int val)
{
    while(pos<=n)
    {
        aib[pos]+=val;
        pos+=pos&-pos;
    }
}

int cauta(int pos)
{
    int s=0;
    while(pos)
    {
        s+=aib[pos];
        pos-=pos&-pos;
    }
    return s;
}

int cautbin(int x)
{
    int aux,pos;
    int ls=1; int ld=n;
    int mij;
    while(ls<=ld)
    {
        mij=(ls+ld)/2;
        aux=cauta(mij);
        if(aux==x)
        {
            pos=mij;
        }
        if(x<=aux)
        {
            ld=mij-1;
        }
        else
        {
            ls=mij+1;
        }
    }
    return pos;

}


int main()
{
    fin>>n;
    for(i=1;i<=n;++i)
    actualizare(i,1);

    pos=2;
    actualizare(pos,-1);
    fout<<pos<<" ";

    for(i=2;i<=n;++i)
    {
        ramaspos=cauta(pos);
        aux=i;
        aux%=n-i+1;
        if(aux==0)
        aux=1;
        if(aux>n-ramaspos)
            aux-=n-ramaspos;
        else
            aux+=ramaspos;

        pos=cautbin(aux);
        actualizare(pos,-1);
        fout<<pos<<" ";
    }
    return 0;
}