Cod sursa(job #2172633)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 15 martie 2018 17:16:12
Problema Schi Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 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];//data de intrare
int arbInter[DMAX*12], sumePoz[DMAX];

void incrementarePoz(int poz){//tot intervalul de la n la 1 este incrementat cu 1
    for(int i = poz; i > 0; i--){
        sumePoz[i] += 1;
    }
}

int primul(int a, int b){
    if(v[a] + sumePoz[a] < v[b] + sumePoz[b]){
        return a;
    }
    return b;
}

void adaugareArboreInter(int pozAct, int st, int dr, int val ,int poz){
    if(st == dr){
        arbInter[pozAct] = val;
        return;
    }
    int mij = (st + dr) / 2;
    if(poz <= mij){
        adaugareArboreInter(pozAct * 2, st, mij, val, poz);
    }else{
        adaugareArboreInter(pozAct * 2 + 1, mij + 1, dr, val, poz);
    }
    arbInter[pozAct] = primul(arbInter[pozAct * 2], arbInter[pozAct * 2 + 1]);
}

void actualizareArbore(int pozAct, int st, int dr){
    if(st == dr){
        return;
    }
    int mij = (st + dr) / 2;
    actualizareArbore(pozAct * 2, st, mij);
    actualizareArbore(pozAct * 2 + 1, mij + 1, dr);
    arbInter[pozAct] = primul(arbInter[pozAct * 2], arbInter[pozAct * 2 + 1]);

}

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

void rezolvare(){
    int nrTot = 0;
    while(nrTot != n){
        int concurent;
        concurent = arbInter[1];
        out << concurent << '\n';
        v[concurent] = DMAX;//scot concurentul din competitie
        incrementarePoz(concurent);
        actualizareArbore(1, 1, n);
        nrTot++;
    }
}


int main(){
    citire();
//    for(int i = 1; i <= n * log2(n); i++){
//        out << arbInter[i] <<' ';
//    }
    rezolvare();
    return 0;
}