Cod sursa(job #994224)

Utilizator enedumitruene dumitru enedumitru Data 5 septembrie 2013 09:52:13
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<fstream>
#define Dmax 30002
using namespace std;
ifstream f("schi.in"); ofstream g("schi.out");
int n,sol,v[Dmax],H[3*Dmax],p[Dmax];
void query(int nod, int st, int dr, int poz)
{   if(st<dr)
		{	int m=(st+dr)>>1;
			if(poz<=H[2*nod])  query(2*nod,st,m,poz);
						else   query(2*nod+1,m+1,dr,poz-H[2*nod]);
		}
	else sol=st;
 }
 void update(int nod, int st, int dr, int poz, int val) 
 {  if(st<dr)
		{	int m=(st+dr)>>1;
			if(poz<=m)   update(2*nod,st,m,poz,val);
					else update(2*nod+1, m+1, dr, poz, val);
			H[nod] = H[2*nod] + H[2*nod+1];
		}
	else H[nod] = val;
}
int main()
{   f>>n;
    for(int i=1; i<=n; i++) f>>v[i], update(1,1,n,i,1);
    for(int i=n; i>=1; i--) 
	{   query(1,1,n,v[i]);          
		update(1,1,n,sol,0);        
        p[sol]=i;
    }
    for(int i=1; i<=n; i++) g<<p[i]<<"\n";
	g.close(); return 0;
}