Cod sursa(job #2176575)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 17 martie 2018 19:23:28
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <iostream>
#include <fstream>
#define DMAX 30001
#define pozBit(x) (x&(-x))

using namespace std;

ifstream in("schi.in");
ofstream out("schi.out");

int n, v[DMAX];
int aib[DMAX], raspuns[DMAX];

void actualizare(int poz, int val){
    for(int i = poz; i <= n; i+=pozBit(i)){
        aib[i] += val;
    }
}

int nrElemInterval(int poz){
    int suma = 0;
    for(int i = poz; i > 0; i-=pozBit(i)){
        suma += aib[i];
    }
    return suma;
}

int cautarePozMin(int val){
    int st = 1, dr = n, pozitie = -1, mij;
    while(st <= dr){
        mij = (st + dr)/2;
        int elementeInterval = nrElemInterval(mij);
        if(elementeInterval == val){
            pozitie = mij;
            dr = mij - 1;
        }else if(elementeInterval < val){
            st = mij + 1;
        }else{
            dr = mij - 1;
        }
    }
    return pozitie;
}

void citire(){
    in >> n;
    for(int i = 1; i <= n; i++){
        in >> v[i];
        actualizare(i, 1);
    }
    in.close();
}

void rezolvare(){
    for(int i = n; i >= 1; i--){
        int elem = cautarePozMin(v[i]);
        raspuns[elem] = i;
        actualizare(elem, -1);//scot elementul din interval
    }
}

void afisare(){
    for(int i = 1; i <= n; i++){
        out << raspuns[i] <<'\n';
    }
}

int main(){
    citire();
    rezolvare();
    afisare();
    return 0;
}