Cod sursa(job #1287456)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 7 decembrie 2014 16:08:59
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <fstream>
#include <vector>
using namespace std;

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

int n, answ, sum;
int poz, val;
int lt, rt;
vector<short> v, a, q;

void UPDATE(int nod, int st, int dr);
void SUM(int nod, int st, int dr);

int main()
{
    is >> n;
    v.resize(n + 1);
    a.resize(4 * n);
    q.resize(n + 1);
    val = 1;
    for ( int i = 1; i <= n; ++i )
    {
        is >> v[i];
        poz = i;
        UPDATE(1, 1, n);
    }
    int st, dr, md;
    lt = 1;
    val = 0;
    for ( int i = n; i; --i )
    {
        st = 1, dr = n;
        answ = 0;
        do
        {
            md = ( st + dr ) / 2;
            rt = md;
            sum = 0;
            SUM(1, 1, n);
            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;
        poz = answ;
        UPDATE(1, 1, n);
    }
    for ( int i = 1; i <= n; ++i )
        os << q[i] << "\n";
    is.close();
    os.close();
    return 0;
}

void UPDATE(int nod, int st, int dr)
{
    if ( st == dr )
    {
        a[nod] = val;
        return;
    }
    int md = ( st + dr ) / 2;
    if ( poz <= md )
        UPDATE(2 * nod, st, md);
    else
        UPDATE(2 * nod + 1, md + 1, dr);
    a[nod] = a[2 * nod] + a[2 * nod + 1];
}

void SUM(int nod, int st, int dr)
{
    if ( lt <= st && dr <= rt )
    {
        sum += a[nod];
        return;
    }
    int md = ( st + dr ) / 2;
    if ( lt <= md )
        SUM(2 * nod, st, md);
    if ( rt > md )
        SUM(2 * nod + 1, md + 1, dr);
}