Cod sursa(job #1253305)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 1 noiembrie 2014 02:32:59
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream is("schi.in");
ofstream os("schi.out");

int n, st, dr, md, answ, sum;
vector<int> v, a, q;

void UPDATE(int poz, int val);
int SUM(int poz);

int main()
{
    is >> n;
    v.resize(n + 1);
    a.resize(n + 1);
    q.resize(n + 1);
    for ( int i = 1; i <= n; ++i )
    {
        is >> v[i];
        UPDATE(i, 1);
    }
    for ( int i = n; i; --i )
    {
        st = 1, dr = n;
        do
        {
            md = ( st + dr ) / 2;
            sum = SUM(md);
            if ( sum >= v[i] )
            {
                if ( sum == v[i] && !q[md] )
                    answ = md, st = dr + 1;
                else
                    dr = md - 1;
            }
            else
                st = md + 1;
        } while ( st <= dr );
        q[answ] = i;
        UPDATE(answ, -1);
    }
    for ( int i = 1; i <= n; ++i )
        os << q[i] << "\n";
    is.close();
    os.close();
    return 0;
}

void UPDATE(int poz, int val)
{
    for ( int i = poz; i <= n; i += i & -i )
        a[i] += val;
}

int SUM(int poz)
{
    int s = 0;
    for ( int i = poz; i; i -= i & -i )
        s += a[i];
    return s;
}