Cod sursa(job #2343452)

Utilizator MaxTeoTeo Oprescu MaxTeo Data 13 februarie 2019 23:29:37
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>
#define lastBit(x) (x & (-x))
using namespace std;

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

const int MAX = 3 * 1e4 + 5;

int n, pas = 1;
int tree[MAX], v[MAX], ans[MAX];

int Query(int idx)
{
    int sum = 0;
    for(; idx; idx -= lastBit(idx))
        sum += tree[idx];
    return sum;
}

void Update(int idx, int val)
{
    for(; idx <= n; idx += lastBit(idx))
        tree[idx] += val;
}

int main()
{
    f >> n;

    for(; pas <= n; pas <<= 1);
    for(int i = 1; i <= n; ++i)
    {
        f >> v[i];
        Update(i, 1);
    }

    for(int i = n; i >= 1; --i)
    {
        int k = 0, step = pas;
        for(; step; step >>= 1)
            if(k + step <= n && Query(k + step) < v[i])
                k += step;
        ans[k + 1] = i;
        Update(k + 1, -1);
    }

    for(int i = 1; i <= n; ++i)
        g << ans[i] << "\n";

    return 0;
}