DMPG '16 S1 - Admin War II

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

FatalEagle and Xyene are squabbling over something petty again, as per tradition, they decided to settle it with a game of Admin War.

Let's revisit the rules of the game. Both players are dealt N (1 \le N \le 100\,000) cards. Players continuously draw cards from the top of their decks and compare their values, and the player whose card has a higher value wins 1 point. In the case of a tie, neither player wins a point. All cards are discarded after being played and the game ends after all N cards have been played. The difference is that this time, they're playing with a deck in which cards can have values from 1 up to 10^9.

You have, once again, taken a peek at their respective cards. However, it seems that they've noticed you this time, and have thus shuffled their decks thoroughly. Unable to determine the outcome of the game, you've decided that you would instead entertain yourself by finding the best possible outcome for each player. Specifically, you would like to know the maximum number of points each player can get in the best case scenario.

Input Specification

The first line of input will have N, the number of cards each player is dealt.

The second line of input will have N space-separated integers, denoting the values of FatalEagle's cards.

The third line of input will have N space-separated integers, denoting the values of Xyene's cards.

Output Specification

Output two integers on separate lines, the maximum number of points that FatalEagle and Xyene can get, respectively.

Sample Input

1 3 5 7 9
2 4 6 8 10

Sample Output


Explanation for Sample Output

A possible optimal situation for FatalEagle is:

7 5 9 3 1
6 4 8 2 10

A possible optimal situation for Xyene is:

10 4 8 6 2
9 3 7 5 1


There are no comments at the moment.