Cod sursa(job #1800817)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 8 noiembrie 2016 09:44:19
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include <climits>
#define ub(x) (x&(-x))

using namespace std;

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

int N, poz, a[30003], AIB[30003], sol[30003];
void mili(int poz) {
    for(int i = poz; i <= N; i += ub(i)) AIB[i]--;
    return;
}

int sum(int poz) {
    int sum = 0;
    for(int i = poz; i >= 1; i -= ub(i)) sum += AIB[i];
    return sum;
}

int bsearch(int x)
{
    int st = 1, dr = N, mij = 0, sumi = 0, MIN = INT_MAX;
    while(st <= dr) {
        mij = (st + dr) / 2;
        sumi = sum(mij);
        if(sumi == x && MIN > mij) MIN = mij;
        else if(sumi >= x)         dr = mij - 1;
        else                      st = mij + 1;
    }
    return MIN;
}
int main()
{
    f >> N;
    for(int i = 1; i <= N; i++) f >> a[i];
    for(int i = 1; i <= N; i++) AIB[i] = ub(i);
    for(int i = N; i >= 1; i--)
        poz = bsearch(a[i]), mili(poz), sol[poz] = i;
    for(int i = 1; i <= N; i++) g << sol[i] << "\n";
    g << "\n";
    return 0;
}