Cod sursa(job #2922733)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 9 septembrie 2022 20:44:16
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>

using namespace std;

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

#define zeros(x)(x & (-x))

const int max_aint = 12e4 + 1;

int aint[max_aint];

void init (int l, int r, int nod)
{
    if (l == r)
    {
        aint[nod] = 1;
    }
    else
    {
        int m = (l + r) / 2;
        init(l, m, 2 * nod);
        init(m + 1, r, 2 * nod + 1);
        aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
    }
}

int update (int l, int r, int poz, int nod)
{
    if (l == r)
    {
        aint[nod] = 0;
        return l;
    }
    else
    {
        aint[nod]--;
        int m = (l + r) / 2;
        if (poz <= aint[2 * nod])
        {
            return update(l, m, poz, 2 * nod);
        }
        else
        {
            return update(m + 1, r, poz - aint[2 * nod], 2 * nod + 1);
        }
    }
}

int main ()
{
    int n;
    in >> n;
    init(1, n, 1);
    int poz = 2;
    for (int i = 1; i <= n; i++)
    {
        poz = (poz + i - 1) % (n - i + 1);
        if (poz == 0)
        {
            poz = n - i + 1;
        }
        out << update(1, n, poz, 1) << " ";
    }
    in.close();
    out.close();
    return 0;
}