Cod sursa(job #2343415)

Utilizator mihailescu_eduardMihailescu Eduard-Florin mihailescu_eduard Data 13 februarie 2019 23:03:00
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>

using namespace std;

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

#define lsb(x) (x&(-x))

static const int NMAX = 3e4+5;

int n;
int aib[NMAX];

void Update(int poz, int val)
{
    for(int i = poz; i<= n; i+=lsb(i))
        aib[i]+=val;
}

int Query(int x)
{
    int sum = 0;
    for(int i =x; i > 0; i-=lsb(i))
        sum+=aib[i];
    return sum;
}

int main()
{
    fin >> n;
    int pas = 1,k,aux, needed, total = 0, rez, poz = 1, nr;
    for(int i =1; i<=n ; ++i)
        Update(i,1);

    for(;pas < n;pas<<=1);
    for(int i =1; i<=n ;++i)
    {
        needed = i % (n-i+1);
        if(!needed)
            needed = n - i + 1;

        nr = Query(n) - Query(poz);
        if(needed <= nr)
            nr = Query(poz) + needed;
        else
            nr = needed - nr;

        poz = 0;
        for(aux = pas; aux; aux >>=1)
            if(aux + poz <= n && Query(aux + poz) < nr)
                poz+=aux;
        ++poz;
        fout<< poz <<" ";
        Update(poz,-1);
        
        
    }
    return 0;
}