Cod sursa(job #918881)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 19 martie 2013 10:44:42
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <cstdio>

using namespace std;


int n, aib[30010];

inline void Update(int poz, int val)
{
    while (poz <= n)
    {
        aib[poz] += val;
        poz = poz + (poz & -poz);
    }
}

inline int Query(int poz)
{
    int rez = 0;
    while (poz)
    {
        rez = rez + aib[poz];
        poz = poz - (poz & -poz);
    }
    return rez;
}

inline int CautareBinara(int val)
{
    int rez, st, dr, mij, x;
    st = 1;
    dr = n;
    while (st <= dr)
    {
        mij = (st+dr)>>1;
        x = Query(mij);
        if (x >= val)
        {
            rez = mij;
            dr = mij - 1;
        }
        else
            st = mij + 1;
    }
    return rez;
}

inline void Read()
{
    ifstream f ("order.in");
    f>>n;
    f.close();
}

inline void Solve()
{
    ofstream g ("order.out");
    int i;
    for (i=1; i<=n; i++)
        Update(i, 1);
    int now, next, inc, total;
    now = 1;
    for (i=1; i<=n; i++)
    {
        inc = Query(now);
        total = Query(n);
        if (total - inc >= i)
        {
            next = inc + i;
        }
        else
        {
            next = i - (total - inc);
            next = next%total;
            if (next == 0)
                next = total;
        }
        now = CautareBinara(next);
        g<<now<<" ";
        Update(now, -1);
    }
    g.close();
}

int main()
{
    Read();
    Solve();
    return 0;
}