A relay coach is assembling a highlight-reel lineup from n runners who ran in a fixed order. Runner i carries a flag color f[i] (either 0 or 1) and has a bib name. The coach wants to choose a subsequence of the runners (keeping their original relative order) such that no two consecutively chosen runners carry the same flag color, and the chosen subsequence is as long as possible. Output the bib names of the chosen runners, in their original relative order.
Line 1: a single integer n — the number of runners.
Line 2: n space-separated integers f[1..n], each 0 or 1 — the flag color of each runner.
Line 3: n space-separated strings, the bib names of each runner in the same order.
Line 1: a single integer k — the number of runners chosen.
Line 2: the k chosen bib names, space-separated, in their original relative order.
Example 1
Input
5 0 0 1 0 1 amir brea cody drew elle
Expected
4 amir cody drew elle
Explanation
Keep amir (flag 0). brea also has flag 0, matching the runner just kept, so keeping her would put two flag-0 runners back to back — she is skipped. cody has flag 1, which differs from the last kept flag (0), so he is kept. drew has flag 0, differing from cody's flag 1, so he is kept. elle has flag 1, differing from drew's flag 0, so she is kept. The final lineup is amir, cody, drew, elle — length 4.
Example 2
Input
3 1 1 1 amir brea cody
Expected
1 amir
Explanation
All three runners carry flag 1. Only amir can be kept as the first pick; brea and cody both share flag 1 with the most recently kept runner, so adding either one would create two same-colored runners in a row. The lineup is just amir — length 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →