Woburn Challenge 2017-18 Round 2 - Senior Division

Problem 1: Keeping Score

There's nothing like a bit of friendly competition, even when your life is on the line! Legolas and Gimli have taken to counting how many enemies they're each able to kill in each confrontation, in an effort to one-up one another.

During the battle of Helm's Deep, Legolas killed L (2 ≤ L ≤ 200,000) enemies, the i-th of which had a strength level of SL_i (1 ≤ SL_i ≤ 10⁹). Meanwhile, Gimli killed G (1 ≤ G < L) enemies, the i-th of which had a strength level of SG_i (1 ≤ SG_i ≤ 10⁹).

Though Gimli killed fewer enemies than Legolas did, he's not about to admit defeat to the elf so easily. As such, he's gotten the idea to introduce a new rule: "All enemies with strength levels smaller than X don't count" (for some positive integer X no larger than 10⁹). Help Gimli find any value of X which would cause him to "win" (in other words, such that Gimli killed strictly more enemies with strength levels greater than or equal to X than Legolas did). If no possible value of X would have this result, output −1 instead.

Subtasks

In test cases worth 7/14 of the points, L ≤ 1000.

Input Format

The first line of input consists of two space-separated integers, L and G.
L lines follow, the i-th of which consists of a single integer SL_i (for i = 1..L).
G lines follow, the i-th of which consists of a single integer SG_i (for i = 1..G).

Output Format

Output a single integer, any valid value of X which would cause Gimli to win, or −1 if there's no such value.

Sample Input 1

5 4
84
6
105
54
30
91
84
28
66

Sample Output 1

60

Sample Input 2

2 1
3 3
3

Sample Output 2

-1

Sample Explanation 2

In the first case, if X = 60, then Legolas's score will be 2 (with his 1st and 3rd killed enemies counting), while Gimli's score will be 3. Note that there exist other valid values of X which would also be accepted.

In the second case, if X ≤ 3, then both Legolas's score will be 2 and Gimli's will be 1. If X > 3, then both scores will be 0. Either way, Gimli can't win.

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 3.00s
Memory Limit: 64M
Added: Feb 23, 2018
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I'm confused why the second line has two numbers whereas the first input doesn't? 

please read the problem statement clearly