Cod sursa(job #1044554)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 30 noiembrie 2013 00:27:45
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>
#include <cstring>

using namespace std ;
const int Nmax = 100004;
int aint[4*Nmax], n;
inline void Update(const int node,const int Left,const int Right,const int pos)
{
    if(Left == Right )
    {
        aint[node] = 0;
        return ;
    }
    int Middle = ( Left + Right )>>1;
    if(pos<=Middle)
        Update(2*node,Left,Middle,pos);
    else
        Update(2*node+1,Middle+1,Right,pos);
    aint[node] = aint[2*node] + aint[2*node+1];
}

inline void Build(const int node,const int Left,const int Right)
{
    if(Left == Right )
    {
        aint[node] = 1;
        return ;
    }
    int Middle = ( Left + Right )>>1;
    Build(2*node,Left,Middle);
    Build(2*node+1,Middle+1,Right);
    aint[node] = aint[2*node] + aint[2*node+1];
}

inline int Query(const int node,const int Left,const int Right,const int x)
{
    if(Left==Right)
        return Left;
    int Middle = (Left + Right)>>1;
    if(x <= aint[2*node])
        return Query(2*node,Left,Middle,x);
    return Query(2*node+1,Middle+1,Right,x-aint[2*node]);
}
inline void Read()
{
    ifstream f("order.in");
    f >> n;
    f.close();
}

inline void Solve()
{
    ofstream g("order.out");
    int i, poz = 2, nr, x;
    Build(1,1,n);
    for(i = 1;i <= n; ++i)
    {
        nr = aint[1];
        poz = poz + i-1;
        while(poz>nr)
            poz -= nr;
        x = Query(1,1,n,poz);
        Update(1,1,n,x);
        g<<x<<" ";
    }
    g<<"\n";
    g.close();
}
int main()
{
    Read();
    Solve();
    return 0;
}