Cod sursă (job #94884)

#include <stdio.h>
#define N_MAX 5000000

int v[N_MAX + 1];
int select(int beg, int end, int k) {
	if (end - beg > 1) {
		int piv = v[(beg * 3 + end * 5) / 8];
		int l = beg - 1, r = end;
		while (l < r) {
			while (v[++l] < piv);
			while (v[--r] > piv);
			if (l < r) {
				int aux = v[l];
				v[l] = v[r];
				v[r] = aux;
			}
		}
		if (k < l) {
			return select(beg, l, k);
		} else {
			return select(l, end, k);
		}
	} else {
		return beg;
	}
}

int main()
{
	FILE *fin, *fout;
	fin = fopen("lalele.in", "r");
	fout = fopen("lalele.out", "w");

	// Citire
	int N, cnt = 0, sp = 0;
	fscanf(fin, "%d", &N);
	while (cnt < N) {
		int x, y;
		fscanf(fin, "%d%d", &x, &y);
		if (y) {
			int j;
			cnt += x;
			for (j = 1; j <= x; j++) {
				v[++sp] = j + y - cnt;
			}
		} else {
			int j;
			for (j = 1; j <= x; j++) {
				int pos = select(1, sp + 1, sp / 2 + 1);
				sp = pos - 1;
				fprintf(fout, "%d\n", v[pos] + (cnt++));
			}
		}
	}

	fclose(fin);
	fclose(fout);
	return 0;
}