Cod sursa(job #2876989)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 23 martie 2022 23:43:47
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("schi.in");
ofstream g ("schi.out");

int n, x;
vector <int> v, bxPerm, bxTree;

void update(int x, int val)
{
    while (x <= n)
    {
        bxTree[x] += val;
        x += (x&-x);
    }
}

int query(int x)
{
    int sol = 0;

    while (x)
    {
        sol += bxTree[x];
        x -= (x&-x);
    }

    return sol;
}

int bs_perm(int val)
{
    int st = 1, dr = n, mij, x = -1, sol, aux;

    while (st <= dr)
    {
        mij = (st + dr) / 2;
        aux = query(mij);

        if (aux == val)
        {
            sol = mij;
            dr = mij - 1;
        }
        else if (aux < val) st = mij + 1;
        else dr = mij - 1;
    }

    return sol;
}

vector <int> solve(vector <int> v)
{
    for (int i = 0; i < n; ++i)
        update(i + 1, 1);

    for (int i = n - 1; i >= 0; --i)
    {
        x = bs_perm(v[i]);
        bxPerm[x] = i + 1;
        update(x, -1);
    }

    for (int i = 1; i <= n; ++i) g << bxPerm[i] << '\n';
}

int main()
{
    f >> n;
    int xInp;
    for (int i = 0; i < n; ++i)
    {
          f >> xInp;

          v.push_back(xInp);
    }

    bxPerm.resize(v.size() + 1);
    fill(bxPerm.begin(), bxPerm.end(), 0);

    bxTree.resize(v.size() + 1);
    fill(bxTree.begin(), bxTree.end(), 0);

    solve(v);

    return 0;
}