Cod sursa(job #2221656)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 15 iulie 2018 12:47:08
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream>
using namespace std;

int k,n, a[3000005];

int find(int l, int r, int k) {
  int mid=a[(l+r)/2];	
 	
  if (k==r-l+1) {
     int maxim = a[l];
	 for (int i=l+1; i<=r; ++i) maxim=max(maxim,a[i]);
	 return maxim;	
  }
  
  int li=l, ri=r;
  
  do {
  	while (a[l]<mid) ++l;
  	while (a[r]>mid) --r;
  	
  	if (l<=r) { swap(a[l],a[r]); ++l; --r; }
  } while (l<=r);
  
  if (a[l]>mid) --l;
  int nr = l-li+1;
  if (nr>=k) return find(li,l,k);
  else return find(l+1,ri,k-nr);
	
}

int main(void) {
	ifstream cin("sdo.in");
	ofstream cout("sdo.out");
	
	cin>>n>>k;
	for (int i=1; i<=n; ++i) cin>>a[i];
	
	cout<<find(1,n,k);
	
	return 0;
}