Cod sursa(job #1830614)

Utilizator mdiannnaMarusic Diana mdiannna Data 16 decembrie 2016 22:15:38
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <iostream>
#include <stdio.h>

using namespace std;
int A[100003], BIT[100003], R[100003];
int N;
/*
void init_BIT(){
    for(int i=1; i<=N; i++)
        BIT[i] = 1;
}
*/


void afisare(){
    for(int i=1; i<=N; i++)
        cout << R[i] << "\n";
}

void afisare_AIB(){
    cout << "AIB:";
    for(int i=1; i<=N; i++)
        cout << BIT[i] << " ";
    cout << "\n";

}

int suma(int i){
    int rez = 0;
    while(i!=0){
        rez += BIT[i];
        i -= i&(-i);
    }
    return rez;
}

void add(int i, int val){
    while(i <= N){
        BIT[i] += val;
        i += i &(-i);
    }
}

void construieste_arbore(){
    for(int i=1; i<=N; i++){
        add(i, 1);
    }
}

void citire(){
    cin >> N;
    for(int i=1; i<=N; i++){
        cin >>A[i];
    }
}


int gaseste(int i, int st, int dr){
    int m = (st+dr)/2;
    if(st == dr)
        return st;
    else
        if(i <= suma(m))
            return gaseste(i, st, m);
        else
            return gaseste(i, m+1, dr);
}

void calc(int i, int val){
    int poz;
    //cout << "val=" << val << endl;
        poz = gaseste(val, 1, N);
        R[poz] = i;
      //  cout << "poz=" << poz << "  i=" << i << endl;;
        add(poz, -1);
}

void schi(){
    R[A[N]] = N;
    add(A[N], -1);
    //cout <<"suma [A[N]]:" << suma(A[N]);
    for(int i = N-1; i>=1; i--){
        calc( i, A[i]);
      }
}


int main()
{
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);

    citire();
    construieste_arbore();
//    init_BIT();
    schi();
    afisare();

    return 0;
}