Cod sursa(job #1830505)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 16 decembrie 2016 20:01:27
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <iostream>
#include <fstream>
#define NMAX 30001
#define lsb(x) (x & (-x))

using namespace std;

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

int AIB[NMAX];
int A[NMAX], n;
int res[NMAX];

void Update(int pos, int val)
{
    for (int i = pos; i <= n; i += lsb(i))
        AIB[i] += val;
}

int Query(int pos)
{
    int sum = 0;
    for (int i = pos; i >= 1; i -= lsb(i))
        sum = sum + AIB[i];
    return sum;
}

int BinarySearch(int k)
{
    int x = 1, y = n;
    int mid;
    while (x <= y)
    {
        mid = (x + y) / 2;
        if (Query(mid) == k && Query(mid - 1) < k)
            return mid;
        else
        {
            if (Query(mid) >= k)
                y = mid - 1;
            else
                x = mid + 1;
        }
    }
    return 0;
}

int main()
{
    in >> n;
    for (int i = 1; i <= n; i++)
    {
        in >> A[i];
        Update(i, 1);
    }
    in.close();
    int pos;
    for (int i = n; i >= 1; i--)
    {
        pos = BinarySearch(A[i]);
        Update(pos, -1);
        res[pos] = i;
    }
    for (int i = 1; i <= n; i++)
        out << res[i] << "\n";
    out.close();
    return 0;
}