Cod sursa(job #2962920)

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

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

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

void Update_AIB(int poz,int val)
{
    for(int i=poz;i<N;i+= (i&(-i)) )
        aib[i]+=val;
}
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;
}