Complaints at IOI University

In IOI University the students are referred to by their exam ranking rather than names. There are \(N\) students numbered from \(0\) to \(N-1\); the student with number \(i\) ranked \(i+1\) in the midterm exam.

For the final exam preparation the students voluntarily form tutoring groups. Each tutoring group is described by two integers \(L\) and \(R\) (with \(0 \le L \le R \le N-1\)). Such a tutoring group consists of all students whose indices are not between \(L\) and \(R\) (inclusive). In other words, the group includes every student \(j\) if \(j R\), and excludes all students \(j\) with \(L \le j \le R\).

On the morning of day \(1\) every student receives an email informing them that at least one tutoring group exists. Then, starting from the evening of day \(d \ge 1\), the following occurs:

• If a student, based on the information they have (i.e. the tutoring groups they belong to and the knowledge of whether any complaint occurred on previous days), deduces that there exists a tutoring group which does not include them, then they consider this unfair and file a complaint before the end of the evening of day \(d\). Immediately after any complaint is made on day \(d\), all tutoring group activities are terminated on the morning of day \(d+1\).
• If no student files a complaint on day \(d\), then the tutoring groups continue to operate into the morning of day \(d+1\). All students also learn that no complaint was submitted on day \(d\).

Note that each student only knows the composition of the tutoring groups they belong to (i.e. the members in those groups) and whether a complaint was filed on any given day – they have no other communication or insight into the existence or membership of the other tutoring groups. The students are perfectly logical and will never deduce an incorrect conclusion.

You are a friend to all the students in IOI University and, as an external observer, you know the complete set of tutoring groups. Given \(M\) tutoring groups represented by the arrays L and R (each of length \(M\)) where the \(i\)-th tutoring group is defined by \(L[i]\) and \(R[i]\) (meaning it excludes students in the range \([L[i], R[i]]\) and includes everyone else), your task is to determine the day \(k\) on which the first complaint is submitted and the list of student indices who submit a complaint on day \(k\).

If no student ever files a complaint then return \(-1\) and an empty list.

Note: Only you as an external helper have the complete information on the tutoring groups. The students do not know the number \(M\) or the details of each group. Also, your submitted code should not perform any input/output operations.

---

Function Specification

pair<int, vector> complaint(int N, vector L, vector R);

The parameters are as follows:

• int N: the total number of students (\(0\) to \(N-1\)).
• vector<int> L and vector<int> R: arrays of size \(M\) defining the tutoring groups. The \(i\)-th group is defined by the range \([L[i], R[i]]\), and consists of all students with indices less than \(L[i]\) or greater than \(R[i]\).

The function should return a pair consisting of:

• An integer \(k\) representing the day on which the complaint(s) are filed. If no complaint ever occurs, \(k = -1\).
• A vector of integers containing the student indices (in ascending order) who file a complaint on day \(k\). The vector size can be at most \(N\). If no complaint occurs, this vector is empty.

Idea / Hint

Although the internal reasoning of the students is complex due to limited information sharing, as an external observer you can compute for each student the earliest day on which they would eventually deduce that a tutoring group exists which excludes them. For each tutoring group, note that it excludes students in the contiguous range \([L[i], R[i]]\) (a total of \(R[i]-L[i]+1\) students). A student who is excluded from a group with \(t\) excluded members would, by logical induction, file a complaint on day \(t\) (if that happens to be the earliest such value among all groups that exclude them). The overall complaint day \(k\) is the minimum among these values over all students, and only those students for whom this minimum is achieved submit a complaint.

inputFormat

The input is provided indirectly by the judge via parameters to the function. The first parameter is an integer \(N\), and the next two parameters are arrays L and R of equal length \(M\), representing the tutoring groups.

For testing purposes, the input format for each test case is as follows (although your solution should not include direct input/output operations):

N
L[0] L[1] ... L[M-1]
R[0] R[1] ... R[M-1]

outputFormat

Your function should return a pair consisting of an integer and a list of integers. The integer represents the day \(k\) on which the complaint is filed (or \(-1\) if no complaint ever occurs), and the list contains the student indices (in increasing order) who submit the complaint on day \(k\).

For testing purposes, the expected output for each test case is as follows (if you were to print the results):

k
student_index_1 student_index_2 ... student_index_p

If \(k = -1\), then no further output is needed.

sample

5
2 0
3 1

2
0 1 2 3

</p>