Cod sursa(job #1658885)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 21 martie 2016 20:53:09
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<fstream>
using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
const int NMAX = 30009;

int AIB[NMAX],v[NMAX],sol[NMAX],N;

int zero(int x)
{

    return (x ^ (x-1)) & x;
}

void update(int x,int val)
{

    for(int i = x ; i <= N ; i += zero(i))
        AIB[i] += val;
}

int suma(int x)
{

    int rez = 0;
    for(int i = x ; i > 0 ; i -= zero(i))
        rez += AIB[i];
    return rez;
}

int query(int K)
{

    int left = 1,right = N,mid,rez;
    while(left <= right){

        int mid = (left + right)>>1;
        int sum = suma(mid);
        if(sum == K)
            rez = mid;
        if(sum < K)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return rez;
}

int main()
{

    in>>N;
    for(int i = 1 ; i <= N; ++i){
        in>>v[i];
        update(i,1);
    }
    for(int i = N ; i > 0 ; --i){

        int val = query(v[i]);
        sol[val] = i;
        update(val,-1);
    }
    for(int i = 1 ; i <= N  ; ++i)
        out<<sol[i]<<"\n";
    in.close();
    out.close();
    return 0;
}