Cod sursa(job #2124230)

Utilizator stefanst77Luca Stefan Ioan stefanst77 Data 7 februarie 2018 00:45:07
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>

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

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

void UpDate(int p, int x)
{
    while (p <= n)
    {
        aib[p] += x;
        p += (p & (-p));
    }
}

void Citire()
{
    int i;
    fin >> n;
    for (i=1; i<=n; i++)
    {
        fin >> a[i];
        UpDate(i, 1);
    }
}

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

int CautaPoz(int x)
{
    int st, dr, p, suma, mid;
    st = 1;
    p = -1;
    dr = n;
    while (st <= dr)
    {
        mid = (st + dr) /2;
        suma = Query(mid);
        if (suma == x)
        {
            p = mid;
            dr = mid - 1;
        }
        else if (suma > x)
            dr = mid - 1;
        else st = mid + 1;
    }
    return p;
}

void Rezolvare()
{
    int i;
    for (i=n; i>=1; i--)
    {
        castig[CautaPoz(a[i])] = i;
        UpDate(CautaPoz(a[i]), -1);
    }
    for (i=1; i<=n; i++)
        fout << castig[i] << "\n";
}

int main()
{
    Citire();
    Rezolvare();
    fin.close();
    fout.close();
    return 0;
}