Let S1 and S2 be two sequences of length n, the elements of which are ordered pairs of integers, not necessarily distinct. Let S1 = (a1,b1),...,(an,bn) and S2 = (c1,d1),...,(cn,dn). The problem is to find permutations p and q of {1,...,n}, if they exist, satisfying the following properties.
1. ap(i) ≤ ap(i+1) and cq(i) ≤ cq(i+1) for 1 ≤ i < n.
2. dq(i) ≤ bp(i) for 1 ≤ i ≤ n.
The second part of the problem, which was not in the ICPC, is to determine whether the solution is unique, that is, there exists exactly one pair of permutations p,q that satisfies the given property.
Input/Output: The first line of input specifies n, which will be at most 5 × 105. The next 4 lines contain n numbers each separated by a space, with each number at most 109. The first line gives the values of ai, the next bi, ci, di in that order. If there exist permutations p,q satisfying the required properties, print p on the first line and q on the second. If there are many solutions, any one is okay. Note that indices are considered from 1 to n. If there are no such permutations, print “impossible”, without quotes. For the second part, if there exist such permutations, print “unique” if the answer is unique, otherwise print “not unique”. Nothing needs to be done if it is impossible. Time limit in the contest was 10sec but it should probably take less. The test cases from the contest,
1
Submission: Submit a single file named RollNo 9.cpp
struct compare{ bool operator()(T const &t1, T const &t2) const {
// comparison for elements of type T } }; sort(v.begin(), v.end(), compare());
// v is a vector of type T, a dummy object of type compare is passed // to the sort function. If f is an object of type compare, f(t1,t2) // returns a boolean value, comparing t1 with t2.
set<T,compare> S;
// defines a set with elements of type T using compare // as the comparison operation.
Sample Input 1 Sample Output 1
4 3 2 4 1
3 2 1 2 4 2 1 3
2 3 4 3 not unique
2 1 2 1
2 2 1 3
Sample Input 2 Sample Output 2
2 1 2
1 2 1 2
2 3 unique
2 8
2 1
2
