Cod sursa(job #2755300)

Utilizator iustin.pericicaPericica Iustin iustin.pericica Data 26 mai 2021 23:08:55
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int m, n;
int arborebinar[400100];
int start, finish;
int maxim;


void Update(int nod, int stanga, int dreapta, int pos){
     if (stanga == dreapta){
          arborebinar[nod]= 0;
          return;
     }

     int div = (dreapta+stanga)/2;
     if (div >= pos) Update(2*nod,stanga,div, pos);
     else   Update(2*nod+1,div+1,dreapta, pos);


    arborebinar[nod] = arborebinar[2*nod + 1] + arborebinar[2*nod];
}



int Query(int nod, int stanga, int dreapta, int x){
     if (stanga == dreapta)
     {
          return dreapta;
     }

     int div = (stanga+dreapta) / 2;
     if (arborebinar[2*nod] >= x) return Query(2*nod, stanga, div, x);
     else return Query(2*nod + 1,div +  1, dreapta, x);
}

void bd(int nod, int stanga, int dreapta){

    if(stanga == dreapta){
        arborebinar[nod] = 1;
        return;
    }
     int div = (stanga+dreapta) / 2;
     bd(2*nod, stanga, div);
     bd(2*nod+1,div+1, dreapta);
     arborebinar[nod] = arborebinar[2*nod] + arborebinar[2*nod+1];

}

int main()
{
    int x, a, b, p=2;


    fin>>n;
    bd(1, 1, n);
    for (int i = 1; i <= n; i++){
        p = p + i - 1;
        while(p > arborebinar[1]){
            p = p - arborebinar[1];
        }
        int rez = Query(1, 1, n, p);
        Update(1, 1, n, rez);
        fout<<rez<<" ";

    }

    return 0;
}