성우님 블로그

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <fstream>
#include <string>
using namespace std;
ifstream fin("input.txt");
ofstream fout("output.txt");

int a[100000],n;

int quick(int low,int high){
	int m,i,j,t,pivot;
	if(high-low>5)
		m=low+rand()%(high-low+1);
	else
		m=(int)((low+high)/2);
	pivot=a[m];
	if(low < high){
	i=low-1;
	j=high+1;
	while(1){
		do{
			i++;
		}while(pivot>a[i]);
		do{
			j--;
		}while(pivot<a[j]);
		if(i>j)
			break;
		else{
			t=a[i]; a[i]=a[j] ; a[j]=t;
		}
	}
	}
	return m;
}	

main(){
	int i,k,low,high,s;
	srand(time(NULL));
	fin >> n;
	for(i=0;i<n;i++)
		fin >> a[i];
	low=0; high=n-1;
	s=int(n*0.2+0.5);
	while(1){
		k=quick(low,high);

		int m,i,j,t,pivot;
		if(high-low>5)
			m=low+rand()%(high-low+1);
		else
			m=(int)((low+high)/2);
		pivot=a[m];
		if(low < high){
		i=low-1;
		j=high+1;
		while(1){
			do{
				i++;
			}while(pivot>a[i]);
			do{
				j--;
			}while(pivot<a[j]);
			if(i>j)
				break;
			else{
				t=a[i]; a[i]=a[j] ; a[j]=t;
			}
		}
		}

		if(m==n-s)
			break;
		else if(m>n-s)
			high=m-1;
		else
			low=m+1;
	}
	fout << a[n-s]  << endl;
}