Cod sursa(job #1793605)

Utilizator SaitamaSaitama-san Saitama Data 31 octombrie 2016 11:25:11
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>
#define nMax 120005

using namespace std;

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

int aint[nMax], n;

inline void Build(int nod, int st, int dr)
{
    if(st == dr)
    {
        aint[nod] = 1;
        return;
    }
    int m = (st + dr) / 2;
    Build(nod * 2, st , m);
    Build(nod * 2 + 1, m + 1, dr);
    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
}

inline void Update(int nod, int st, int dr, int p)
{
    if(st == dr)
    {
        aint[nod] = 0;
        return;
    }
    int m = (st + dr) / 2;
    if(p <= m)
        Update(nod * 2, st, m, p);
    else Update(nod * 2 + 1, m + 1, dr, p);
    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
}

inline int Querry(int nod, int st, int dr, int k)
{
    if(st == dr)
        return st;
    int m = (st + dr) / 2;
    if(k <= aint[nod * 2])
        return Querry(nod * 2, st, m, k);
    else return Querry(nod * 2 + 1, m + 1, dr, k - aint[nod * 2]);
}

inline void Solve()
{
    int i, poz, p;
    Build(1, 1, n);
    poz = 2;
    for(i = 1; i <= n ;i++)
    {
        poz = poz + i - 1;
        while(poz > aint[1])
            poz -= aint[1];
        p = Querry(1, 1, n, poz);
        fout << p << " ";
        Update(1, 1, n, p);
    }
    fout << "\n";
}

int main()
{
    fin >> n;
    Solve();
    fin.close();fout.close();
    return 0;
}