Cod sursa(job #3261275)

Utilizator Carnu_EmilianCarnu Emilian Carnu_Emilian Data 5 decembrie 2024 09:10:59
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fcin("schi.in");
ofstream fcout("schi.out");

const int N = 1e5 + 5;
int aib[N], sol[N], v[N], n;
/**
8
1 1 3 4 4 2 1 3

1 2 3 4 5 6 7 8
7 2 8 6 1 3 5 4

1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0
*/
void Update(int poz, int x)
{
    while (poz <= n)
    {
        aib[poz] += x;
        poz += (poz & -poz);
    }
}

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

int cb(int x)
{
    int st, dr, m, p;
    st = 1;
    dr = n;
    p = -1;
    while (st <= dr)
    {
        m = (st + dr) / 2;
        int r = Query(m);
        if (r == x)
        {
            p = m;
            dr = m - 1;
        }
        else if (r < x)
            st = m + 1;
        else
            dr = m - 1;
    }
    return p;
}

int main()
{
    int x, tip, a, b;
    fcin >> n;
    for (int i = 1; i <= n; i++)
    {
        fcin >> v[i];
        Update(i, 1);
    }
    for (int i = n; i >= 1; i--)
    {
        int p = cb(v[i]);
        sol[p] = i;
        Update(p, -1);
    }
    for (int i = 1; i <= n; i++)
        fcout << sol[i] << '\n';

    return 0;
}