Cod sursa(job #2833407)

Utilizator borcanirobertBorcani Robert borcanirobert Data 15 ianuarie 2022 10:50:19
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

int N;
vector<int> a;
vector<int> aib;
vector<int> res;

// x[pos] += val
void update(int pos, int val);

// calculeaza suma x[1] + x[2] + ... + x[n]
int query(int x);

void ReadData();
void Solve();

int Search(int pos);        // cauta a pos-a pozitie libera

int main()
{
    ReadData();
    Solve();

    fin.close();
    fout.close();
    return 0;
}

void ReadData()
{
    fin >> N;
    res = a = aib = vector<int>(N + 1);
    for (int i = 1; i <= N; ++i)
    {
        fin >> a[i];
        update(i, 1);
    }
}

void Solve()
{
    for (int i = N; i >= 1; --i)
    {
        int pos = Search(a[i]);
        res[pos] = i;
        update(pos, -1);
    }

    for (int i = 1; i <= N; ++i)
        fout << res[i] << '\n';
}

int Search(int pos)
{
    int l{1}, r{N}, mid, ans;

    while (l <= r)
    {
        mid = (l + r) / 2;
        int q = query(mid);

        if (q >= pos)
        {
            r = mid - 1;
            if (q == pos)
                ans = mid;
        }
        else
            l = mid + 1;
    }

    return ans;
}

void update(int pos, int val)
{
    for (int i = pos; i <= N; i += i & (-i))
        aib[i] += val;
}

int query(int x)
{
    int res = 0;
    for (int i = x; i > 0; i -= i & (-i))
        res += aib[i];
    
    return res;
}