Cod sursa(job #969148)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 3 iulie 2013 16:51:02
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
/* AIB */

#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <ctime>
#include <utility>

using namespace std;

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

const int MAXN = 30005;
int N, AiB[MAXN], P[MAXN], C[MAXN];

void Update(int x, int y)
{
    while(x <= N)
    {
        AiB[x] += y;
        x += (x^(x-1))&x;
    }
}
int Query(int x)
{
    int sum = 0;
    while(x)
    {
        sum += AiB[x];
        x -= (x^(x-1))&x;
    }
    return sum;
}

int Search(int x)
{
    int li = 1, ls = N , mij, fin;
    while( li <= ls )
    {
        mij = ((li+ls)>>1);
        int nowsum = Query(mij);
        if( nowsum >= x )
        {
            ls = mij - 1;
            if(nowsum == x)
                fin = mij;
        }
        else li = mij + 1;
    }
    return fin;
}

int main()
{
    cin >> N;
    for(int i = 1 ; i <= N ; ++ i)
        cin >> C[i];
    cin.close();
    for(int i = 1 ; i <= N ; ++ i)
        Update(i, 1);

    for(int i = N ; i ; -- i)
    {
        int p = Search(C[i]);
        P[p] = i;
        Update(p, -1);
    }
    for(int i = 1; i <= N ; ++ i)
        cout << P[i] << "\n";
    cout << "\n";
    cout.close();

    return 0;
}