Cod sursa(job #1509092)

Utilizator EpictetStamatin Cristian Epictet Data 23 octombrie 2015 14:54:59
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <fstream>

using namespace std;

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

int n, AIB[100010];

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

void Update(int poz, int value)
{
    while (poz <= n)
    {
        AIB[poz] += value;
        poz += zeros(poz);
    }
}

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

inline int Binary_Search(int value, int st, int dr)
{
    int step = 1, ok = 0;
    while (step <= dr) step <<= 1;

    while (step)
    {
        step >>= 1;
        if (dr - step >= st)
        {
            int aux = Query(dr - step) - Query(st - 1);
            if (aux >= value)
            {
                dr -= step;
                ok = 1;
            }
        }
    }
    if (ok) return dr;
    return 0;
}

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

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

        if (Binary_Search(1, ppp + 1, n))
        {
            ppp = Binary_Search(1, ppp + 1, n);
        }
        else
        {
            ppp = Binary_Search(1, 1, ppp);
        }


        if (Binary_Search(aux, ppp, n))
        {
            ppp = Binary_Search(aux, ppp, n);
        }
        else
        {
            aux -= Query(n) - Query(ppp - 1);
            ppp = Binary_Search(aux, 1, ppp);
        }

        fout << ppp << ' ';
        Update(ppp, -1);
        m --;
    }

    fout.close();
    return 0;
}