CCO '24 P2 - Pizza Party

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 4.0s
Memory limit: 1G

Problem type

Troy is fleshing out the details of his latest initiative, HackCCO! Everyone knows that the biggest appeal of any hackathon is the free food. As such, to ensure the unparalleled success of HackCCO, Troy ordered a comically large cart stacked with N pizzas where the i-th pizza from the top of the cart has flavour a_i.

After the pizza cart arrives, Troy needs to arrange them into some number of stacks on a long table. To do this, he takes the pizzas one-by-one from the top of the cart and moves them onto the table, each time either placing the pizza on top of another stack of pizzas or forming a new stack on the table.

The N hungry HackCCO participants are lined up to get pizza from the table, one-by-one. Troy knows that the i-th person in line has a favourite pizza flavour of b_i. When the i-th person walks up to the table, if they see any pizzas of their favourite flavour at the top of any stack they will take any one of them at random. Otherwise, they won't take anything and will leave the table hungry.

Of course, hungry coders are not happy coders, so Troy doesn't want anyone to leave the table hungry. Thus, he asks you to help him find an arrangement of pizzas on the table such that it is possible for nobody to leave hungry. Furthermore, out of all such arrangements, Troy wants you to find one that creates the smallest number of stacks on the table (after all, tables can only get so long). Help him find such an arrangement or determine that it's impossible!

Input Specification

The first line of input contains a single integer N.

The second line of input contains N space-separated integers a_1, \ldots, a_N (1 \le a_i \le N).

The third line of input contains N space-separated integers b_1, \ldots, b_N (1 \le b_i \le N).

Marks Awarded Bounds on N Additional constraints
3 marks 1 \le N \le 10^6 1 \le a_i, b_i \le 2
4 marks 1 \le N \le 5\,000 All a_i are distinct
5 marks 1 \le N \le 10^6 All a_i are distinct
6 marks 1 \le N \le 5\,000 None
7 marks 1 \le N \le 10^6 None

[Post-CCO edit: Subtasks 4 and 5 may not be solvable efficiently. CCO competitors were judged only on subtasks 1-3.]

Output Specification

If it is impossible to arrange the pizzas as desired, output -1.

Otherwise, your output should consist of three lines.

On the first line, output K, the minimum number of stacks required.

On the second line, output N space-separated integers c_1, \ldots, c_N (1 \le c_i \le K), indicating that the i-th pizza should be placed on stack c_i.

On the third line, output N space-separated integers d_1, \ldots, d_N (1 \le d_i \le K), indicating that the i-th person in line takes their pizza from the d_i-th stack.

This stack must have a pizza of flavour b_i at the top when the i-th participant walks up to get their pizza.

Sample Input 1

7
1 2 3 2 2 1 3
2 3 1 2 3 2 1

Sample Output 1

2
1 2 1 2 1 2 2
1 2 2 2 1 2 1

Explanation for Sample 1

An illustration of the arrangement of pizzas on the table is shown above where red, yellow, and blue boxes represent pizzas of flavours 1, 2, and 3 respectively.

Sample Input 2

2
1 2
1 1

Sample Output 2

-1

Comments

There are no comments at the moment.