Cod sursa(job #1623947)

Utilizator qwertyuiTudor-Stefan Berbinschi qwertyui Data 1 martie 2016 22:55:15
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 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 <= NMAX)
    {
        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;

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

        if (bsearch == x)
			return middle;

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

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] <<' ';

    return 0;
}