Cod sursa(job #3255723)

Utilizator EricDimiericdc EricDimi Data 12 noiembrie 2024 09:39:59
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>
#define lsb(x) x & -x

using namespace std;

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

const int MAX_N = 3e6;

int aib[MAX_N + 1];
int sol[MAX_N + 1];
int loc[MAX_N + 1];
int n, maxp2;

void update(int pos, int val)
{
    for (int i = pos; i <= n; i += lsb(i))
        aib[i] += val;
}

int query(int pos)
{
    int sum = 0;
    for (int i = pos; i > 0; i -= lsb(i))
        sum += aib[pos];
    return sum;
}

int cb(int x)
{
    int step = maxp2, sum = 0, p = 0;
    while (step > 0)
    {
        if (p + step <= n && sum + aib[p + step] < x)
        {
            sum += aib[p + step];
            p += step;
        }
        step >>= 1;
    }
    return p + 1;
}

int main()
{
    f >> n;

    maxp2 = 1;
    while ((maxp2 << 1) <= n)
        maxp2 <<= 1;

    for (int i = 1; i <= n; i++)
    {
        f >> loc[i];
        update(i, 1);
    }

    for (int i = n; i > 0; i--)
    {
        int pos = cb(loc[i]);
        sol[pos] = i;
        update(pos, -1);
    }

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

    f.close();
    g.close();
    return 0;
}