Cod sursa(job #1366379)

Utilizator bugyBogdan Vlad bugy Data 28 februarie 2015 23:46:03
Problema Statistici de ordine Scor 50
Compilator java Status done
Runda Arhiva educationala Marime 1.27 kb
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;


public class Main {
	public static int[] v;
	public static int k;
	
	public static int quickSelect() {
		int left = 0, right = v.length-1;
		k --;
		
		while (left < right) {
			int l = left, r = right;
			int mid = v[(int)(l+r)/2];
			
			
			while (l < r) {
				if (v[l] >= mid) {
					int aux = v[r];
					v[r] = v[l];
					v[l] = aux;
					r--;
				} else {
					l++;
				}
			}
			if (v[l] > mid) {
				l--;
			}
			if (k <= l) {
				right = l;
			} else {
				left = l+1;
			}
		}
		return v[k];
	}

	
	public static void main(String[] args) throws IOException {
		
		BufferedReader buffer = new BufferedReader(new FileReader("sdo.in"));
		
		String[] line = buffer.readLine().split(" ");
		
		int n = Integer.parseInt(line[0]);
		k = Integer.parseInt(line[1])+1;
		
		line = buffer.readLine().split(" ");
		v = new int[n+1];
		for (int i = 0; i < n; i++) {
			v[i] = Integer.parseInt(line[i]);
		}
		
		buffer.close();
		
		BufferedWriter out = new BufferedWriter(new FileWriter("sdo.out"));
		
		out.write(Integer.toString(quickSelect()));
		out.write("\n");
		
		out.close();
	}
}