Permeowtation 3

View as PDF

Submit solution

Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

After its citizens were fully vaccinated, the COVID-19 pandemic on the cat planet was finally defeated, and life is gradually getting back to normal. To celebrate the victory, the royalties of cat planet organized a sport event with many different games, one of which is called Permeowtation (courtesy of Neko) with the rules as follows:

Initially, the athlete is given two permutations ~a~ and ~b~, both having length ~n~. The athlete needs to merge these two permutations together to make an array ~c~ consisting of ~2 \cdot n~ elements with the following procedure:

  • Initially, array ~c~ is empty.

  • The athlete performs ~2\cdot n~ steps. At each step, the athlete chooses either array ~a~ or array ~b~, erase the first element of the chosen array, and append this element into ~c~. Note that the chosen array must contain at least one element.

The athlete will be awarded a prestigious medal from the cat planet sports federation, if the array ~c~ created by the athlete contains no two consecutive elements of equal value. In other words, the athlete needs to create an array ~c~ satisfying ~c_i \ne c_{i + 1}~ for every ~1 \le i < 2 \cdot n~.

Mike, a young but enthusiastic athlete in this sport, has tried very hard to prepare for the best. But before the stage, Mike felt nervous and suddenly forgot the best strategy to win the game. Please help Mike play this game and win a medal!

Definition. A permutation is an array consisting of ~n~ distinct integers from ~1~ to ~n~ in arbitrary order. For example, ~[2,3,1,5,4]~ is a permutation, but ~[1,2,2]~ is not a permutation (~2~ appears twice in the array) and ~[1,3,4]~ is also not a permutation (~n=3~ but there is ~4~ in the array)


The first line contains a single integer ~n~ (~2 \le n \le 10^5~), the length of ~a~ and ~b~.

The second line contains ~n~ distinct integers ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le n~).

The third line contains ~n~ distinct integers ~b_1, b_2, \ldots, b_n~ (~1 \le b_i \le n~).


Output ~2n~ characters a or b, with the ~i~-th character denoting the array that should be chosen in the ~i~-th step.

It can be shown that the answer always exists with the given constraints.


  • Subtask 1 (~15~ points): ~n = 2~

  • Subtask 2 (~15~ points): ~n \le 10~

  • Subtask 3 (~20~ points): No additional constraints

The total score for this problem is ~50~.

Sample Input 1

1 2 3
3 2 1

Sample Output 1


Sample Input 2

2 1
1 2

Sample Output 2



In the first example, array ~a~ has the value ~[1, 2, 3]~ and array ~b~ has the value ~[3, 2, 1]~.

With the given example output, array ~c~ has the value ~[1, 3, 2, 3, 2, 1]~.


Please read the guidelines before commenting.

  • -28
    vncharles  commented on June 21, 2022, 3:06 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.