Problem A
Employee Promotion

This problem is a tutorial for Kattis. If you’ve used Kattis or similar online judges before (codeforces, atcoder, etc…) skip to the input.

The first thing you want to do for any problem is read the input. On Kattis, input is provided through stdin. Here are common ways to read input for python, java, and cpp:

Python:

Read 1 line (as a string): input()

Read 1 line that consists of 1 integer: n = int(input())

Read 1 line that consists of [for example] 3 integers: a, b, c = map(int, input().split())

Read 1 line that consists of an array of integers: arr = list(map(int, input().split()))

Read the entire input into an array of lines: inp = os.read(0, 10 ** 9).decode("utf-8").split("\n") (when the input is large ($\sim 10^6$))

Note the integers must be space separated

Java:

Refer to https://codeforces.com/blog/entry/7018

C++:

Read 3 integers (don’t have to be on the same line):

int a, b, c;
cin >> a >> b >> c;

Read an array of integers of length $n$:

vector<int> arr(n);
for (int i = 0; i < n; ++i) cin >> arr[i];

Read a string (containing no whitespace):

string s;
cin >> s;

When you’ve written a program to determine the answer, you will need to output to stdout. Here are common ways to write to stdout for python, java, and cpp.

Python:

Print 3 integers separated by spaces: print(a, b, c)

Print an array of things on one line separated by spaces: print(" ".join(map(str, arr)))

Java:

Refer to https://codeforces.com/blog/entry/7018

C++:

Print int/string/character separated by spaces: cout << i << " " << s << " " << c << "\n";

Print array of ints on one line separated by spaces:

for (int i: arr) cout << i << " ";
cout << "\n";

(the trailing space is usually fine)

How do you know if your code is fast enough? Use this as a rule of thumb:

Take the maximum input bounds and plug them into your time complexity. For example, if the input consists of integers $n, m < 1000$ and your code is $O(n * m * log_2(n + m))$, plugging in $1000$ for $n$ and $m$ your code will take $~ 10^7$ “operations.” Here are the (rough) upper bounds for # of “operations” that will pass under standard time constraints:

Python:

$10^7$, but no recursion or higher order functions

In general python recursion is extremely slow. In addition, if your recursion stack can grow large it is recommended to do

import sys
sys.setrecursionlimit(10 ** 6)

Java: $10^8$

C++: $2 \cdot 10^8$

For more information see:

https://np-compete-2021.kattis.com/help/python3

https://np-compete-2021.kattis.com/help/java

https://np-compete-2021.kattis.com/help/cpp

https://np-compete-2021.kattis.com/help

Other notes:

You can only import things in the standard library. For python, this means no numpy, for cpp this means no boost (although you can use bits/stdc++ and ext/pb_ds).

Now, for the problem

John is determining which employees to promote. He decides to promote employees who score higher than some threshold $k$ on their performance reports. John is extremely successful so he has a large number of employees working for him. John is also lazy (he says it’s the key to his success) so he wants you to write a program to tell him which people are getting promoted.

Input

The first line contains integers $n$ (the number of employees John has) and $k$ (the performance threshold), $1 \leq n \leq 10 ^5, -10^9 \leq k \leq 10^9$. The next line is an array of $n$ space separated distinct names of John’s employees (strings). The next line is an array $a$ of $n$ space separated integers, where the $i$th integer is the performance score of the $i$th employee. $ -10^9 \leq a_ i \leq 10^9$.

Output

Output the names of the people John will promote (those who have scored > k) in the order they first appear, one per line.

4 6
Liam Noah Emma Eva
1 10 9 5

Noah
Emma