Processing math: 100%
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 ith doll perform the jth chore, the efficiency would be Ai,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 ith line contains n integers Ai,j. ### Output - The first line print the maximum efficiency to complete n chores. - The next n lines, the ith line is the chore to which doll i was assigned. If there are multiple ways to arrange chores, print any. ### Constraints - 1≤n≤200. - 1≤Ai,j≤109. ### Example Input: 4944128781322836737 Output: 71234
Topic
Binary search
Graph
Flow
Rating 1600
Solution (0) Solution