COCI '17 Contest 6 #6 Vrtić

View as PDF

Submit solution

All submissions

Best submissions

Points: 25 (partial)

Time limit: 1.0s

Memory limit: 256M

Problem types

There are $N$ ~N~ children in a kindergarten, and each child considers one child to be their best friend. Children are quite unusual, so it holds that no two children consider the same child their best friend, but it is possible that a child is a best friend to themself! Additionally, if child $B$ ~B~ is best friend of child $A$ ~A~, $A$ ~A~ is not necessarily best friend of child $B$ ~B~.

The kindergarten teacher has $N$ ~N~ bags of candy that she wishes to distribute to the children such that each child gets exactly one bag. However, the problem is that the bags don't necessarily contain the same amounts of candy, so the children can become displeased. Since the children have a very developed sense of justice, the dissatisfaction of child $A$ ~A~ is equal to the absolute difference between the number of candy $A$ ~A~ and their best friend received.

The kindergarten teacher has decided to distribute the bags so that the maximal dissatisfaction of a child is as small as possible. Help her determine the optimal distribution of candy bags!

Input Specification

The first line of input contains the integer $N$ ~N~ $(1 \le N \le 150)$ ~(1 \le N \le 150)~.

The second line of input contains $N$ ~N~ distinct integers, whereas the $i^\text{th}$ ~i^\text{th}~ number is the label of the best friend of the $i^\text{th}$ ~i^\text{th}~ child. The children are labelled with numbers from $1$ ~1~ to $N$ ~N~.

The third line of input contains $N$ ~N~ integers, whereas the $i^\text{th}$ ~i^\text{th}~ number is equal to the number of candy in the $i^\text{th}$ ~i^\text{th}~ bag. The numbers won't exceed $10^9$ ~10^9~.

Output Specification

The first line of output must contain the minimum possible maximal dissatisfaction of a child.

The second line of output must contain $N$ ~N~ numbers, separated by space, whereas the $i^\text{th}$ ~i^\text{th}~ number denotes the number of candy for the $i^\text{th}$ ~i^\text{th}~ child. If there are multiple optimal distributions, output any.

Scoring

In test cases worth $20\%$ ~20\%~ of total points, the best friend of the $i^\text{th}$ ~i^\text{th}~ child will be the $(i+1)^\text{th}$ ~(i+1)^\text{th}~ child for all $i < N$ ~i < N~, and the best friend of the $N^\text{th}$ ~N^\text{th}~ child will be the first child.