Оптимизация по памяти алгоритма пойска k-той статистики (Язык C)

[PathTheir]

Добрый вечер.

Сидел я тут, решал задачки с тимуса, наткнулся на задачку, решение которой мне показалось достаточно тривиально - используем алгоритм поиска k-той статистики.

Только после написания программы я обратил внимание на ограничения по памяти - 1 мегабайт. Путем несложных вычислений (250 000 * 4 байта (тип int) = 1 000 000 байт / 1024 / 1024 = 0,95 мегабайт) понимаем, что хранение массива чисел практически полностью съедает наше ограничение по памяти, а, так как 1 мегабайт выделяется на весь процесс, мы получаем Memory Limit на 7 тесте.

В итоге задача была решена другим, менее красивым способом, но все таки хочется добить ее именно этим алгоритм.

Поэтому хотелось бы узнать, возможна ли здесь оптимизация по памяти, чтобы этот алгоритм прошел?

Вот код программы + снизу ссылка на ideone, если кому-то там удобнее

#include <stdio.h>

#define SIZE 250000

int a[SIZE], n;

long search_statistics(int l, int r, int k)
{
	while (l < r)
	{
		int i = l, j = r;
		int x = a[(r - l) / 2 + l];

		while (i <= j)
		{
			while (a[i] < x) i++;

			while (a[j] > x) j--;

			if (i <= j)
			{
				int t = a[i];
				a[i++] = a[j];
				a[j--] = t;
			}
		}

		if (k <= j)
			r = j;
		else if (k >= i)
			l = i;
		else
			break;
	}

	return a[k];
}

int main()
{
	int i;
	long double res;

	scanf("%d", &n);

	for (i = 0; i < n; i++)
		scanf("%d", &a[i]);

	if (n % 2)
		res = search_statistics(0, n - 1, n / 2);
	else
		res = ((long double) search_statistics(0, n - 1, n / 2) / 2) + ((long double) search_statistics(0, n - 1, n / 2 - 1) / 2);
	
	printf("%.1Lf", res);

	return 0;
}

http://ideone.com/3WJtgy

[PathTheir]

Да, еще подумал, что возможно для этого следует хранить не весь массив.

[kostan3]

простите что не на с
(язык g++ 4.7.2 (работаеь и на с++))
вот рабочий код :

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

priority_queue<int> q;

int main() {
	int n, x;
	double ans = 0.0;
	scanf("%d", &n);
	int m = n / 2 + 1;
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		q.push(x);
		if (q.size() > m) q.pop();
	}
	ans = q.top();
	q.pop();
	if (n % 2 == 0) ans = (q.top() + ans) / 2;
	printf("%.1f\n", ans);
	return 0;
}