Cod sursa(job #1623967)

Utilizator qwertyuiTudor-Stefan Berbinschi qwertyui Data 1 martie 2016 23:07:49
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

#define NMAX 30050

int input[NMAX], tree[NMAX], ranking[NMAX];
int N;

void Update (int pos, int value)
{
    while (pos <= N)
    {
        tree[pos] += value;
        pos += (pos&(-pos));
    }
}

int Query (int pos)
{
    int sum = 0;
    while (pos > 0)
	{
        sum += tree[pos];
        pos -= (pos&(-pos));
	}
	return sum;

}

int BSearch (int x)
{
    int left = 1, right = N, solution = -1;

    while (left <= right)
	{
        int middle = (left + right) / 2;
        int bsearch = Query(middle);

        if (bsearch == x)
		{
			solution = middle;
			right = middle - 1;
			continue;
		}

		if (bsearch > x)
			right = middle - 1;
		else
			left = middle + 1;

	}

	return solution;

}

int main()
{
    fin >>N;

	for (int i = 1; i <= N; ++i)
	{
        fin >>input[i];
        Update(i,1);
	}

	for (int i = N; i >= 1; --i)
	{
        int pos = BSearch(input[i]);
        ranking[pos] = i;
        Update(pos, -1);
	}

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

    return 0;

}