Cod sursa(job #918895)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 19 martie 2013 10:54:23
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.24 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); /// pun copiii in aib
    int now, next, inc, total;
    now = 1;
    for (i=1; i<=n; i++)
    {
        inc = Query(now); /// inc = numarul de copii pe care ii am pana acum, dupa ultima eliminare
        total = Query(n); /// total = cati copii mai am in total in momentul de fata
        if (total - inc >= i)
        {
            /// acum trebuie sa elimin al i-lea copil;
            /// daca imi ajung copiii pana la final atunci atunci elimin al i-lea copil de unde am ramas
            /// adica de la inc

            next = inc + i;
        }
        else
        {
            /// daca nu am destui copii ca sa il elimin pe al i-lea pana la capat,
            /// trebuie sa trec peste cei pe care ii am pana la capat (total - inc)
            /// si acum ar trebui sa elimin al 9i - (total - inc)) - lea copil pe care la fel nu stiu daca il am
            /// pana la capat asa ca fac modulo total.
            next = i - (total - inc);
            next = next%total;
            if (next == 0)
                next = total;
        }
        now = CautareBinara(next); /// caut binar pozitia (cea mai din stanga) unde am al i-lea copil;
        g<<now<<" ";
        Update(now, -1); /// scot copilul bagat
    }
    g.close();
}

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