Cod sursa(job #2101244)

Utilizator nic_irinaChitu Irina nic_irina Data 7 ianuarie 2018 00:08:12
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <iostream>
#include <fstream>
using namespace std;

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

int v[30001], aib[30001], clasament[30001];
int n;

///tata[i] = i+=(i&-i)
///anterior[i] = i-(i&-i)

void update(int k)
{
    int i;
    for(i=k; i<=n; i+=(i&-i)) //se duce din tata in tata
        aib[i]--;
}

int query(int k)
{
    int ans=0, i;
    for(i=k; i>=1; i-=(i&-i))  //se duce din fiu in fiu
        ans += aib[i];
    return ans;
}

int caut_bin (int st, int dr, int k)
{
    int m;
    //pt ca sigur o sa gaseasca nr de pozitii corespunzatoare
    while(st <= dr)
    {
        m = ( st + dr ) / 2;  //overflow: st+(dr-st)/2
        int libere = query(m);
        if(libere < k)
            st = m+1;
        else
            dr = m-1;

    }
    update(dr+1);
    return dr+1;
}


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

    for(i=1; i<=n; i++)
        aib[i]=(i&-i);

    //for(i=1; i<=n; i++)
        //cout<<aib[i]<<" ";

    for(i=n; i>=1; i--)
    {

        int poz = caut_bin(1, n, v[i]);
        clasament[poz]=i;
        /*if ( query( v[i] ) == v[i] )
        {
            update(v[i]);
            clasament[i] = i;
        }
        else
        {
            int poz = caut_bin(v[i], n, v[i]);
            clasament[poz] = i;
        }*/

    }
    for(i=1; i<=n; i++)
        fout<<clasament[i]<<'\n';
    return 0;
}