Cod sursa(job #344031)

Utilizator nautilusCohal Alexandru nautilus Data 28 august 2009 11:51:22
Problema Schi Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<fstream.h>

int a[30005],poz[30005];

int divide(int p, int q)
{
 int st=p,dr=q,x=poz[p],y=a[p];
 
 while (st<dr)
	 {
	  while (st<dr && poz[dr]>=x)
		  dr--;
	  poz[st]=poz[dr]; a[st]=a[dr];
	  while (st<dr && poz[st]<=x)
		  st++;
	  poz[dr]=poz[st]; a[dr]=a[st];
	 }
 poz[st]=x; a[st]=y;
 
 return st;
}

void qsort(int p, int q)
{
 int m=divide(p,q);
 
 if (m-1>p)
	 qsort(p,m-1);
 if (m+1<q)
	 qsort(m+1,q);
}

int main()
{
 int n,i,j,x;
	
 ifstream fin("schi.in");
 fin>>n;
 for (i=1; i<=n; i++)
	 {
	  a[i]=i;
	  fin>>x;
	  poz[i]=x;
	  if (x<i)
		  for (j=1; j<=i-1; j++)
			  if (poz[j]>=x)
				  poz[j]++;
	 }
 
 qsort(1,n);
 
 ofstream fout("schi.out");
 for (i=1; i<=n; i++)
	 fout<<a[i]<<'\n';
 
 fin.close();
 fout.close();
 
 return 0;
}