Cod sursa(job #1838717)

Utilizator BLz0rDospra Cristian BLz0r Data 1 ianuarie 2017 17:03:50
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <fstream>
#include <algorithm>
using namespace std;

#define NMAX 30002
#define LSB(x) ( (x) & -(x) )

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

int N, v[NMAX], AIB[NMAX], Sol[NMAX];
bool Ocupat[NMAX];

// uodate pe pozitie
inline void AddVal(int pos, int val) {

    for (int i = pos; i <= N; i += LSB(i))
        AIB[i] += val;
}

// suma pe intervalul 1...pos
inline int GetSum(int pos) {

    int res = 0;

    for (int i = pos; i > 0; i -= LSB(i))
        res += AIB[i];

    return res;
}

int Bsearch(int val) {

    int st = 1, dr = N;

    while (st <= dr) {

        int mid = (st + dr) >> 1;

        int x = GetSum(mid);

        if (x < val) {
            st = mid + 1;
            continue;
        }

        if (x > val) {
            dr = mid - 1;
            continue;
        }

        if (x == val) {
            if (Ocupat[mid])
                dr = mid - 1;
            else
                return mid;
        }
    }
}

int main() {

    fin >> N;

    //consider cate un schior pe fiecare pozitie
    for (int i = 1; i <= N; ++i) {
        fin >> v[i];
        AddVal(i, 1);
    }

    // plec de la coada la cap, pentru ca asa am certitudine despre pozitia finala
    for (int i = N; i >= 1; --i) {
        int poz = Bsearch(v[i]); // caut binar a v[i] -a pozitie neocupata din clasament
        Sol[poz] = i;
        AddVal(poz, -1);
        Ocupat[poz] = 1;
    }

    for (int i = 1; i <= N; ++i)
        fout << Sol[i] << "\n";

    return 0;
}