Cod sursa(job #2755337)

Utilizator RobertLitaLita Robert RobertLita Data 26 mai 2021 23:51:24
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("order.in");
ofstream g("order.out");

int n, m, arbore[400000], poz, start, finish, maxim;
void update(int nod, int st, int dr)
{
    if(st == dr){
        arbore[nod] = 0;
        return;
    }
    int mij = (st + dr) / 2;
    if(poz <= mij)update(2 * nod, st, mij);
    else update(2 * nod + 1, mij + 1, dr);
    arbore[nod] = arbore[nod * 2] + arbore[nod * 2 + 1];
}
int query(int nod, int st, int dr, int x)
{
    if(st == dr){
        return dr;
    }
    int mij = (st + dr) / 2;
    if(arbore[2 * nod] >=x )return query(2 * nod, st, mij, x);
    else return query(2 * nod + 1, mij + 1, dr, x - arbore[2 * nod]);
}

void sum(int nod, int st, int dr)
{
    if(st == dr){
        arbore[nod] = 1;
        return ;
    }
    int mij = (st + dr) / 2;
    sum(2 * nod, st, mij);
    sum(2 * nod + 1, mij + 1, dr);
    arbore[nod] = arbore[2 * nod] + arbore[2 * nod +1];
}
int main()
{
    int x, k = 2;
    f >> n;
    sum(1, 1, n);
    for(int i = 1; i <= n; i++){
        k = k + i - 1;
       while(k > arbore[1]){
            k = k - arbore[1];
       }
       x = query(1, 1, n, k);
       poz = x;
       update(1, 1, n);
       g << x << ' ';
    }
    return 0;
}