Pagini recente » Borderou de evaluare (job #2331353) | Cod sursa (job #2761303)
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int arb[130000],pas,n;
ifstream fin("order.in");
ofstream fout("order.out");
//cream arborele astfel incat in fiecare nod sa retinem numarul de fii pe care ii are acel nod
void creare_arbore(int nod, int st, int dr)
{
if(st==dr)
arb[nod] = 1;
else
{
int mij = (st+dr)/2;
creare_arbore(nod*2,st,mij);
creare_arbore(nod*2+1,mij+1,dr);
arb[nod]= arb[nod*2]+arb[nod*2+1];
}
}
void update(int nod, int st, int dr, int p)
{
if(st==dr)//daca st = dr inseamna ca am ajuns la o frunza si trebuie sa o eliminam
{
arb[nod] = 0;
fout<<st<<" ";
}
else
{
int mij = (st+dr)/2;
if(arb[nod*2]!=0)//daca fiul stang e diferit de 0 atunci verificam daca pozitia p este mai mica ca numarul de fii din stanga
//si daca este, inseamna ca trebuie sa eliminam un copil din subarborele stang
{
if(p<=arb[nod*2])
{
update(nod*2,st,mij,p);
arb[nod] = arb[nod*2]+arb[nod*2+1];
}
else//daca pozitia p este mai mare inseamna ca sarim peste toti copii din subarborele stang si de aceea scadem pozitia cu numarul de fii din subarborele stang
//si cautam in subarborele drept
{
p = p-arb[nod*2];
update(nod*2+1,mij+1,dr,p);
arb[nod] = arb[nod*2]+arb[nod*2+1];
}
}
else//daca fiul stang = 0 inseamna ca singurul loc in care mai putem cauta este in dreapta
{
update(nod*2+1,mij+1,dr,p);
arb[nod] = arb[nod*2]+arb[nod*2+1];
}
//dupa fiecare update actualizam si valorile noi ale nodurile
}
}
int main()
{
fin>>n;
creare_arbore(1,1,n);
pas = 2;
int contor = 1;
cout<<arb[1];
//variabila pas numara cati pasi au fost facuti pana acum si atunci cand este mai mare decat numarul de copii o reducem pana ce ajunge la numarul de copii potriviti
while(arb[1]>0)
{
pas = pas+contor;
pas--;
while(pas>arb[1])
pas=pas-arb[1];
update(1,1,n,pas);
contor++;
}
return 0;
}