Cod sursa(job #2019668)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 8 septembrie 2017 12:01:53
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include<fstream>
#include<climits>
#define ub(x)(x&(-x))
using namespace std;ifstream f("schi.in");ofstream g("schi.out");int N,AIB[30003],a[30003],sol[30003];void add(int poz,int val){for(int i=poz;i<=N;i+=ub(i))AIB[i]+=val;}
int sum(int poz){int s=0;for(int i=poz;i>0;i-=ub(i))
s+=AIB[i];return s;}
int cautbin(int x){int st=1,dr=N,ans=INT_MAX,mij=0;while(st<=dr){mij=(st+dr)/2;int nr=sum(mij);if(nr==x&&mij<ans){ans=mij;}
else if(nr<x)st=mij+1;else dr=mij-1;}
return ans;}
int main()
{f>>N;for(int i=1;i<=N;i++)
AIB[i]=ub(i),f>>a[i];for(int i=N;i>=1;i--){int poz=cautbin(a[i]);add(poz,-1);sol[poz]=i;}
for(int i=1;i<=N;i++)
g<<sol[i]<<"\n";return 0;}