Pagini recente » Cod sursa (job #2783040) | Cod sursa (job #2894429) | Solutii preONI 2008, Runda 1 | Cod sursa (job #2120640) | Cod sursa (job #2022954)
#include <fstream>
#include <stdlib.h>
#include <string.h>
#define nmax 30005
using namespace std;
fstream f1("schi.in", ios::in);
fstream f2("schi.out", ios::out);
int n, sol[nmax], q[nmax], aib[nmax];
///aib[x]= suma el de pe intervalul [x-2^k +1.. x] din vect initial 1 1 1 1 1 1 1 1
///cauti a q[i]-a valoare de 1 de la stanga la dreapta binar
///sum in aib de la 1 la mijl=q[i] si mijl minim
///aceasta e poz cautata
///apoi pui pe 0 pozitia q[i]
void adauga(int poz, int val)
{
///adaugi val la toate intervalele cu propr ca: au capat dr>=x si in contin pe x
///acestea sunt de la aib[x] , aib[x+2^k],... aib[valmax]
while(poz<=n)
{
aib[poz]+=val;
poz=2*poz-(poz&(poz-1));
}
}
void citire()
{
int i;
f1>>n;
for(i=1; i<=n; i++)
{
f1>>q[i];
adauga(i, 1);
}
}
void afis()
{
int i;
for(i=1; i<=n; i++)
f2<<sol[i]<<"\n";
}
int sum(int poz) ///suma in aib de la poz 1 la poz
{
int su=0;
while(poz>0)
{
su+=aib[poz];
poz=poz& (poz-1);
}
return su;
}
int cauta_in_sum(int st, int dr, int val)
{
if(st<=dr)
{
int mijl=(st+dr)/2, x=sum(mijl);
if((x==val)&&((mijl==1)||(sum(mijl-1)<val))) return mijl;
else if(x<val) return cauta_in_sum(mijl+1, dr, val);
else return cauta_in_sum(st, mijl-1, val);
}
}
void solutie()
{
int i, poz;
for(i=n; i>=1; i--)
{
poz=cauta_in_sum(1, n, q[i]);
sol[poz]=i;
adauga(poz, -1);
}
}
int main()
{
citire();
solutie();
afis();
return 0;
}