Cod sursa(job #2901776)

Utilizator DafinaTrufasTrufas Dafina DafinaTrufas Data 14 mai 2022 13:52:33
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <iostream>
#include <fstream>
using namespace std;

int a[30000], d[120000], clas_fin[30000];

void creare(int nod, int st, int dr)
{
    if(st == dr)
    {
        d[nod] = a[st];
        return;
    }
    creare(nod * 2, st, (st + dr) / 2);
    creare(nod * 2 + 1, (st + dr) / 2 + 1, dr);
    d[nod] = d[nod * 2] + d[nod * 2 + 1];
}

void modif(int nod, int st, int dr, int i, int val)
{
    if(i < st || i > dr) return;
    if(st == dr)
    {
        d[nod] = val;
        return;
    }
    modif(nod * 2, st, (st + dr) / 2, i, val);
    modif(nod * 2 + 1, (st + dr) / 2 + 1, dr, i, val);
    d[nod] = d[nod * 2] + d[nod * 2 + 1];
}

int fixare_poz(int nod, int st, int dr, int poz_interm)
{
    if(st == dr)
        return st;
    if(d[2*nod] < poz_interm)
        return fixare_poz(nod * 2 + 1, (st + dr) / 2 + 1, dr, poz_interm - d[nod * 2]);
    // daca, la momentul curent, nu mai sunt suficiente pozitii libere in intervalul din fiul stang,
    // inseamna ca pozitia finala a schiorului curent se gaseste in intervalul din fiul drept
    return fixare_poz(nod * 2, st, (st + dr) / 2, poz_interm);
}

int main()
{int n, i, p;
ifstream f("schi.in");
ofstream g("schi.out");
f >> n;
for(i = 1; i <= n; i++)
    a[i] = 1;
creare(1, 1, n); // initial, toate pozitiile din clasament sunt necompletate
for(i = 1; i <= n; i++)
    f >> a[i];
for(i = n; i >= 1; i--)
{
    p = fixare_poz(1, 1, n, a[i]);
    clas_fin[p]=i;
    modif(1, 1, n, p, 0); // pe masura ce fixez pozitiile in clasament, setez respectivele pozitii ca fiind imposibil
                          // de ocupat de catre schiorii pentru care calculez ulterior
}
for(i = 1; i <= n; i++)
    g << clas_fin[i] << '\n';
f.close();
g.close();
return 0;
}