Cod sursa(job #2061369)

Utilizator trifangrobertRobert Trifan trifangrobert Data 9 noiembrie 2017 09:59:57
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
#define DIM 30010

using namespace std;

int n, v[DIM], rez[DIM], aib[DIM];

void Read()
{
    ifstream fin("schi.in");
    fin >> n;
    for (int i = 1;i <= n;++i)
        fin >> v[i];
    fin.close();
}

void Update(int poz, int val)
{
    while(poz <= n)
    {
        aib[poz] += val;
        poz += (poz & -poz);
    }
}

int Query(int poz)
{
    int s = 0;
    while(poz > 0)
    {
        s += aib[poz];
        poz -= (poz & -poz);
    }
    return s;
}

int BinarySearch(int val)
{
    int left = 1, right = n, mid, poz = -1, ret, aux;
    while(left <= right)
    {
        mid = (left + right) / 2;
        aux = Query(mid);
        if (aux == val)
        {
            ret = mid;
            right = mid -1;
        }
        else if (aux < val)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return ret;
}

void Solve()
{
    for (int i = 1;i <= n;++i)
        Update(i, 1);
    int x;
    for (int i = n;i >= 1;--i)
    {
        x = BinarySearch(v[i]);
        rez[x] = i;
        Update(x, -1);
    }
}

void Write()
{
    ofstream fout("schi.out");
    for (int i = 1;i <= n;++i)
        fout << rez[i] << "\n";
    fout.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}