Cod sursa(job #2761303)

Utilizator Virgil993Virgil Turcu Virgil993 Data 1 iulie 2021 15:40:43
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 kb
#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;
}