Cod sursa(job #2124087)

Utilizator loo_k01Luca Silviu Catalin loo_k01 Data 6 februarie 2018 21:06:16
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <bits/stdc++.h>
#define Nmax (int(3 * 1e4) + 3)

using namespace std;

int a[Nmax];
int sol[Nmax];
int aib[Nmax];
int n;

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

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

int BinarySearch(int S)
{
    int st, dr, mid, Suma, p;
    st = 1; dr = n;
    p = -1;
    while (st <= dr)
    {
        mid = (st + dr) / 2;
        Suma = Query(mid);

        if (Suma == S)
        {
            p = mid;
            dr = mid - 1;
        }
        else if (Suma > S) dr = mid - 1;
        else st = mid + 1;
    }
    return p;
}

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

void Afisare()
{
    int i;
    for (i = 1; i <= n; i++)
        cout << aib[i] << " ";
}

void Solve()
{
    int poz, i;
    for (i = n; i >= 1; i--)
    {
        poz = BinarySearch(a[i]);
        sol[poz] = i;
        Update(poz, -1);
    }

    ofstream fout("schi.out");
    for (i = 1; i <= n; i++)
        fout << sol[i] << "\n";
    fout.close();
}

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