Cod sursa(job #1509093)

Utilizator zacuscaAlex Iordache zacusca Data 23 octombrie 2015 14:55:23
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <fstream>

using namespace std;

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

int n, AIB[30003];

inline int zeros (int x)
{
    return x & (-x);
}

inline void Update (int poz, int val)
{
    for (; poz <= n; poz += zeros(poz))
    {
        AIB[poz] += val;
    }
}

inline int Query (int poz, int sum = 0)
{
    for (; poz; poz -= zeros (poz))
    {
        sum += AIB[poz];
    }

    return sum;
}

inline int BinSearch (int val, int st, int dr)
{
    int step;
    bool gasit =false;
    for (step = 1; step <= dr; step <<= 1);

    while (step)
    {
        step >>= 1;
        if (dr - step >= st)
        {
            int aux = Query (dr - step) - Query (st - 1);
            if ( aux >= val)
            {
                dr -= step;
                gasit = true;
            }
        }

    }
    if (gasit == true) return dr;
    return 0;
}

int main ()
{
    in >> n;

    for (int i = 1; i <= n; i++)
        {
            Update (i, 1);
        }

    int ramase = n, pos = 1;
    for (int i = 1; i <= n; i++)
    {
        int aux = i;
        aux %=  ramase;
        if (!aux) aux = ramase;

        if (BinSearch(1, pos +1, n))
        {
            pos = BinSearch(1, pos +1, n);
        }
        else
        {
            pos = BinSearch(1, 1, pos);
        }

        if (BinSearch(aux, pos, n))
        {
            pos = BinSearch(aux, pos, n);
        }
        else
        {
            aux -= Query(n) - Query(pos - 1);
            pos = BinSearch(aux, 1, pos);
        }

        Update (pos, -1);
        ramase --;

        out << pos << ' ';
    }
}