Cod sursa(job #2962945)

Utilizator and_Turcu Andrei and_ Data 9 ianuarie 2023 20:32:32
Problema Schi Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 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);
vector< bool > ap(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 k,int poz)
{
    int index=0,sum=0;
    for(int i=logMAX;i>=0;i--)
    {
        int p=(1<<i);
        if( index+p<=n and sum+aib[index+p]==k and !fr[index+p] )
        {
            ap[index]=1;
//    fout << index+p << "\n";
            return index+p;
        }
        if( index+p<=n and sum+aib[index+p]<k )
        {
            sum+=aib[index+p];
            index+=p;
        }

    }

    return index;
}

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] ,i);
//        if( fr[pozitie] )cout << "pula   " << i << "\n";
        fr[pozitie]=i;
        Update_AIB(pozitie,-1);
    }
    for(int i=1;i<=n;i++)fout << fr[i] << "\n";
    fout.close();
    return 0;
}