Cod sursa(job #2312504)

Utilizator mirunaFmiruna mirunaF Data 4 ianuarie 2019 22:44:10
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <iostream>
#include <fstream>

using namespace std;

const int N = 30002;

int AIB[N], *v, *sol;

void Update ( int poz, int x )
{
    while ( poz < N )
    {
        AIB[poz] += x;
        poz = poz + (poz & (-poz));
    }
}

int Suma (int poz)
{
	int s = 0, i = poz;
    while (i > 0){
		s += AIB[i];
		i = i - (i & (-i));
    }
	return s;
}

int Cautare ( int st, int dr, int poz)
{
    long long pas = 1 << 20;
    int r = st;
    while(pas > 0)
    {
        if( pas + r <= dr && Suma(pas + r) < v[poz] )
            r += pas;
        pas = pas / 2;
    }
    return r;
}

int main()
{
    ifstream in ("schi.in");
    ofstream out ("schi.out");

    int poz, n, i;

    in >> n;
    v = new int [n + 1];
    sol = new int [n + 1];
    for ( i = 1; i <= n; i++ )
    {
        Update(i, 1);
        in >> v[i];
    }

    for(i = n ; i > 0; i--)
    {
        poz = Cautare (1, n, i);
        sol[poz] = i;
        Update(poz, -1);
    }

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

    in.close();
    out.close();

    return 0;
}