Cod sursa(job #2801636)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 16 noiembrie 2021 17:59:31
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int arbint[100005];

void precalc(int nod, int st, int dr)
{
    if(st == dr)
    {
        arbint[nod] = 1;
        return;
    }
    int med = (st + dr) / 2;
    precalc(2 * nod, st, med);
    precalc(2 * nod + 1, med + 1, dr);
    arbint[nod] = arbint[2 * nod] + arbint[2 * nod + 1];
}

void update(int nod, int st, int dr, int val)
{
    if(st == dr)
    {
        arbint[nod] = 0;
        fout << st << ' ';
        return;
    }
    int med = (st + dr) / 2;
    if(val <= arbint[2 * nod])
        update(2 * nod, st, med, val);
    else
        update(2 * nod + 1, med + 1, dr, val - arbint[2 * nod]);
    arbint[nod]--;
}


int main()
{
    int last, free, n;
    fin >> n;
    precalc(1, 1, n);
    free = n;
    last = 2;
    for(int i = 1; i <= n; i++)
    {
        last = (i + last - 1) % free;
        if(last == 0)
            last = free;
        update(1, 1, n, last);
        free--;
    }
    return 0;
}