Description
This problem is a simple application of the set data structure. The rst part is from the ICPC world nals 2019. The actual description of the problem can be found at https://icpc.kattis.com/problems/azulejos. A more formal description is given below.
Let S_{1} and S_{2} be two sequences of length n, the elements of which are ordered pairs of integers, not necessarily distinct. Let S_{1} = (a_{1}; b_{1}); : : : ; (a_{n}; b_{n}) and S_{2} = (c_{1}; d_{1}); : : : ; (c_{n}; d_{n}). The problem is to nd permutations p and q of f1; : : : ; ng, if they exist, satisfying the following properties.

^{a}p(i)^{a}p(i+1) ^{and} ^{c}q(i) ^{c}q(i+1) ^{for 1} ^{i < n.}

d_{q(i)} b_{p(i)} for 1 i n.
In other words, the elements in S_{1} and S_{2} must be ordered in nondecreasing order of their rst coordinate, such that the ith element in the ordering of S_{2} has second coordinate less than or equal to the second coordinate of the ith element in the ordering of S_{1}. Such orderings may not always be possible.
The basic algorithm is as follows. Let a be the minimum value of the a_{i} and c the minimum of the c_{i}. Let A be the subset of pairs in S_{1} whose rst coordinate is equal to a, and C the subset of pairs in S_{2} with rst coordinate c. The elements in A must come rst in the ordering of S_{1} and the elements in C must come rst in the ordering of S_{2}. Suppose jAj jC j. Then for every element of A the corresponding element in the ordering of S_{2} must be an element in C. Choose an element in C such that its second coordinate is the largest possible but does not exceed the second coordinate of the element in A. Delete these elements from A and C. If for some element in A, no such element in C is found, then an ordering is not possible. If A becomes empty, some elements may be left in C. Now consider the second smallest value of the rst coordinate in S_{1}, let A be the set of those elements and repeat. If jCj jAj, do the same for elements in C, except that the element of A chosen is the one with smallest second coordinate that is greater than or equal to the second coordinate of the element in C. The lower bound and/or upper bound methods of the set class can be used to nd these elements.
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 satis es the given property.
Input/Output: The rst line of input speci es n, which will be at most 5 10^{5}. The next 4 lines contain n numbers each separated by a space, with each number at most 10^{9}. The rst line gives the values of a_{i}, the next b_{i}, c_{i}, d_{i} in that order. If there exist permutations p; q satisfying the required properties, print p on the rst 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
for the rst part, are put up on teams. I may use di erent ones, especially for the second part.
Submission: Submit a single le named RollNo 9.cpp
Note: It may be necessary to compare ordered pairs of numbers based on the rst coordinate, or the second coordinate at di erent times. (It may in fact be easier to consider triples, where the third coordinate is the index). By default, sets and functions like sort use the < operator for comparison. If a di erent comparison function is required, it can be speci ed when de ning the set or calling the sort function. This is done using function objects, for which the function call operator () is de ned. A sample declaration would be
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 
impossible 

2
2 3
2 8
2 1
2