Cod sursa(job #2029843)

Utilizator FrequeAlex Iordachescu Freque Data 30 septembrie 2017 15:38:05
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <iostream>
#include <fstream>

using namespace std;

const int NMAX = 30000 + 5;

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

int n;
int v[NMAX], table[NMAX];
int AIB[NMAX];
bool vis[NMAX];

int zeros(int x)
{
    return x^(x&(x - 1));
}

void read()
{
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
}

int query(int poz)
{
    int rez = 0;
    for (int i = poz; i >= 1; i -= zeros(i))
        rez += AIB[i];
    return rez;
}

void update(int poz, int val)
{
    for (int i = poz; i <= n; i += zeros(i))
        AIB[i] += val;
}

int find_key(int x)
{
    int st = 1, dr = n, mijl, pos;
    while (st <= dr)
    {
        mijl = (st + dr) / 2;
        if (query(mijl) >= x)
        {
            pos = mijl;
            dr = mijl - 1;
        }
        else
        {
            st = mijl + 1;
        }
    }
    return pos;
}

void write()
{
    for (int i = 1; i <= n; ++i)
        fout << table[i] << "\n";
}

int main()
{
    read();
    for (int i = 1; i <= n; i++) update(i, 1);
    for (int i = n; i >= 1; --i)
    {
        int index = find_key(v[i]);
        update(index, -1);
        table[index] = i;
    }
    write();

    return 0;
}