Cod sursa(job #2962922)

Utilizator and_Turcu Andrei and_ Data 9 ianuarie 2023 19:47:30
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <bits/stdc++.h>
#define N 30000
#define logMAX 11
using namespace std;

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

vector<int> aib(N+7,0);
vector<int> fr(N+7,0);
vector< int > a(N+7,0);
int n;

void Update_AIB(int p, int x)
{
    while (p<=n)
    {
        aib[p]+=x;
        p+=(p&(-p));
    }

}
int Query_AIB(int poz)
{
    int ans=0;
    for(int i=poz;i>=1;i-= (i&(-i)) )
        ans+=aib[i];
    return ans;
}

int Search_AIB(int val)
{
    int poz=0;
    int st=1,dr=n,mij;
    while( st<=dr )
    {
        mij=(st+dr)/2;
        int x=Query_AIB(mij);
        if( x==val )
        {
            poz=mij;
            dr=mij-1;
        }
        else if( x>val )
            dr=mij-1;
        else if( x<val )
            st=mij+1;
    }
    return poz;
}

int main()
{
    fin >> n;
    for(int i=1;i<=n;i++)
    {
        fin >> a[i];
        Update_AIB(i,1);
    }
    fin.close();
    for(int i=n;i>=1;i--)
    {
        int pozitie;
        pozitie= Search_AIB( a[i] );
        Update_AIB(pozitie,-1);
        fr[pozitie]=i;
    }
    for(int i=1;i<=n;i++)fout << fr[i] << "\n";
    fout.close();
    return 0;
}

//
//int Suma(int p)
//{
//    int s=0;
//    while (p>0)
//    {
//        s+=aib[p];
//        p-=(p&(-p));
//    }
//    return s;
//}
//
//int CautBin(int x)
//{
//    int st=1,dr=n,mij,poz=-1,s;
//    while (st<=dr)
//    {
//        mij=(st+dr)/2;
//        s=Suma(mij);
//        if (s==x)
//        {
//            poz=mij;
//            dr=mij-1;
//        }
//        else if (s<x) st=mij+1;
//        else dr=mij-1;
//    }
//    return poz;
//}
//int main()
//{
//    int poz,x,i;
//    fin >> n;
//    for (i=1; i<=n; i++)
//    {
//        fin >> a[i];
//        update(i,1);
//    }
//    for (i=n; i>=1; i--)
//    {
//        poz=CautBin(a[i]);
//        update(poz,-1);
//        sol[poz]=i;
//    }
//    for (i=1; i<=n; i++)
//        fout << sol[i] << "\n";
//
//    return 0;
//}
//
//