Cod sursa(job #2124300)

Utilizator calinfloreaCalin Florea calinflorea Data 7 februarie 2018 08:40:23
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>
#define NMax 100006
using namespace std;

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

int aib[NMax], n, castig[NMax], a[NMax];

void Update(int p, int x)
{
    for(int i = p; i <= n; i += (i & (-i)))
        aib[i] += x;
}

int Query(int p)
{
    int sum = 0;

    for(int i = p; i >= 1; i -= (i & (-i)))
        sum += aib[i];
    return sum;
}

int CautBin(int s)
{
    int st = 1;
    int dr = n;
    int mid, suma = 0, poz = -1;

    while(st <= dr)
    {
        mid = (st + dr) / 2;
        suma = Query(mid);
        if(suma == s)
        {
            poz = mid;
            dr = mid - 1;
        }
        else if(suma > s)
            dr = mid - 1;
        else
            st = mid + 1;

    }
    return poz;
}
void Citire()
{
    int i;

    fin >> n;

    for(i = 1; i <= n; i++)
    {
        fin >> a[i];
        Update(i, 1);
    }

}

void Rezolva()
{
    int i, r;

    for(i = n; i >= 1; i--)
    {
        r = CautBin(a[i]);
        castig[r] = i;
        Update(r, -1);
    }

    for(i = 1; i <= n; i++)
        fout << castig[i] << "\n";
}
int main()
{
    Citire();
    Rezolva();
    return 0;
}