Submission #46749950

---

Source Code Expand

#include <stdio.h>
#include <stdlib.h>

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return a < b ? -1 : a > b;
}

int N, M;
int A[212345];
int B[212345];

/* A_i 円以上なら売る → A_i が小さいほど売ってもらいやすい */
int get_urite(int x) {
	int yes = 0, no = N - 1;
	if (x < A[0]) return 0;
	if (A[N - 1] <= x) return N;
	while (yes + 1 < no) {
		int m = yes + (no - yes) / 2;
		if (A[m] <= x) yes = m; else no = m;
	}
	return yes + 1;
}

/* B_i 円以下なら買う → B_i が大きいほど買ってもらいやすい */
int get_kaite(int x) {
	int no = 0, yes = M - 1;
	if (B[M - 1] < x) return 0;
	if (x <= B[0]) return M;
	while (no + 1 < yes) {
		int m = no + (yes - no) / 2;
		if (x <= B[m]) yes = m; else no = m;
	}
	return M - yes;
}

int main(void) {
	int i;
	int no = 0, yes = 1010101010;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
	}
	for (i = 0; i < M; i++) {
		if (scanf("%d", &B[i]) != 1) return 1;
	}
	qsort(A, N, sizeof(*A), cmp);
	qsort(B, M, sizeof(*B), cmp);
	while (no + 1 < yes) {
		int m = no + (yes - no) / 2;
		if (get_urite(m) >= get_kaite(m)) yes = m; else no = m;
	}
	printf("%d\n", yes);
	return 0;
}

Submission Info

Judge Result