That Kind of Relationship
Time limit4.242sMemory limit1042 MB
Construct a permutation of 1..N whose number of inversions equals K, for N up to 4242.
- Level
Medium5 of 10
- Topics
- Greedy, Implementation, Math, Combinatorics
- Solved
- No attempts yet
Problem
Hwanju, the most sociable person in Sinsu-dong, is popular again today. The popularity is so great that Hwanju's name pours out every day in the bamboo forest.
Hwanju had a secret to that popularity: the ability to make any two people he wants into that kind of relationship!
Hwanju's method for making that kind of relationship is as follows.
- Line up people in a row, from person to person .
- Give each person a slip of paper with one of the positive integers from to written on it. The integers on the slips do not repeat.
- When two different people are chosen, if the person on the left has a larger integer on their slip than the person on the right, those two people are in that kind of relationship.
- Surprisingly, one person can be in that kind of relationship with several people.
Hwanju, the 21st century's Cupid, is worn out from too many consultations about crushes and romance. So Hwanju wants to make several that kind of relationships at once. But making too many harms public morals, and making too few leaves many singles, so he wants to make exactly that kind of relationships.
Hwanju saw friends running from far away. If he does not quickly make that kind of relationships, they might become Hwanju's anti-fans!
Input
Integers and are given. (, )
Output
Output integers separated by spaces.
is the integer on the slip that person received, and exactly that kind of relationships must be made.
A way to make exactly that kind of relationships always exists, and if there are several ways, output one of them.