Cod sursa(job #853962)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 12 ianuarie 2013 16:49:12
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#define NMAX 500001

using namespace std;

ifstream input("algsort.in");
ofstream output("algsort.out");

unsigned int tree[1 << 20];
int N;
const unsigned int Infinit = 2147483648;

void delete_from_tree(int nod , int left , int right , const unsigned int value)
{
    if (left == right)
    {
         tree[nod] = value;
    }
    else
    {
        int middle = (left + right) >> 1;
        int left_son = nod << 1;
        int right_son = left_son + 1;

        if (tree[left_son] < tree[right_son]) delete_from_tree(left_son , left , middle , value);
        else delete_from_tree(right_son , middle + 1, right , value);

        tree[nod] = min(tree[left_son] , tree[right_son]);
    }
}


void update_tree(int nod , int left , int right , const unsigned int value , int A)
{
    if (left == right)
    {
        tree[nod] = value;
    }
    else
    {
        int middle = (left + right) >> 1;
        int left_son = nod << 1;
        int right_son = left_son + 1;
        if (A <= middle) update_tree(left_son , left , middle , value , A);
        if (A > middle) update_tree(right_son , middle+1 , right , value , A);

        tree[nod] = min(tree[left_son] , tree[right_son]);
    }
}

int main()
{
    input >> N;
    for (int i =1;i<=N;i++)
    {
        int x;
        input >> x;
        update_tree(1,1,N,x,i);
    }
    for (int i =1;i<=N;i++)
    {
        output << tree[1] << " ";
        delete_from_tree(1,1,N,Infinit);
    }
    input.close();
    output.close();
    return 0;
}