Chores 2 - MarisaOJ: Marisa Online Judge

Chores 2

Time limit: 1000 ms
Memory limit: 256 MB
Today, Marisa visited Alice at her house. Alice was busy assigning chores to her collection of $n$ dolls, with $n$ chores in total. She knows that if the $i^{th}$ doll perform the $j^{th}$ chore, the efficiency would be $A_{i,j}$. The efficiency of $n$ dolls equal to the minimum efficiency among the dolls. A doll can be assigned at most $1$ chore, and a chore can be assign at most $1$ times. However, Alice does not know the maximum efficiency possible. Therefore, she has asked Marisa for help, and Marisa is turning to you for assistance. ### Input - The first line contains an integer $n$. - The next $n$ lines, the $i^{th}$ line contains $n$ integers $A_{i,j}$. ### Output - The first line print the maximum efficiency to complete $n$ chores. - The next $n$ lines, the $i^{th}$ line is the chore to which doll $i$ was assigned. If there are multiple ways to arrange chores, print any. ### Constraints - $1 \le n \le 200$. - $1 \le A_{i,j} \le 10^9$. ### Example Input: ``` 4 9 4 4 12 8 7 8 13 2 2 8 3 6 7 3 7 ``` Output: ``` 7 1 2 3 4 ```
Topic
Binary search
Graph
Flow
Rating 1600
Solution (0) Solution