CS3233 Midterm Team Contest sponsored by Citadel | Citadel Securities


2020-03-02 00:50 AKST

CS3233 Midterm Team Contest sponsored by Citadel | Citadel Securities


2020-03-02 05:20 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -442 days 9:31:08

Time elapsed


Time remaining


Problem G
She's All Yak

The Fetlock Fete is a traditional Ponyville promenade: a large party where partners perform in several dances!

\includegraphics[width=0.4\textwidth ]{TBO_Yak.png}
Figure 1: Illustration by Kyle Coate.

Yona was invited by Sandbar to this year’s Fetlock Fete, and, naturally, she wants him to see her best side. To this end, she hopes to carefully choose which of the dances to participate in, and which ones to sit out, such that she and Sandbar have the best time at the event.

This year’s Fetlock Fete will contain $N$ dances, played in sequence. There are many types of dances: the cotillion, the waltz, and so on, so for simplicity, we will simply denote each type with a positive integer. The $i^\text {th}$ of the dances at the event is of type $C_ i$.

Yona has looked through the list and has rated each dance with her perceived level of flair $S_ i$. The level of flair encompasses all things about the dance: how well she can perform it, how much she thinks Sandbar likes it, among other things. A higher level of flair indicates a more desirable dance.

Now, Yona needs help choosing which dances to perform. To make sure she and Sandbar have the best time at the event, she wants to stick to the following rules:

  1. She cannot perform a dance if its type is the same as the type of the most recent dance she performed.
    (Sandbar might lose interest if they perform the same type of dance twice in a row.)

  2. She cannot perform a dance if its level of flair is lower than or equal to any dance she has performed before.
    (Sandbar should be gradually more impressed as the night progresses.)

  3. She wants to perform the maximum number of dances possible following the two rules above.
    (Sandbar will surely be bored if they sit out too many dances!)

Can you help her make the decisions?


The first line of input contains two integers, $N$ ($1 \leq N \leq 300\, 000$) and $M$ ($1 \leq M \leq N$), the number of dances in the Fetlock Fete, and the number of different types of dances, respectively.

The next $N$ lines of input contain the descriptions of the dances. In particular, the $i^\text {th}$ of these lines contains two integers $C_ i$ ($1\leq C_ i \leq M$) and $S_ i$ ($1 \leq S_ i \leq 10^9$), denoting that the $i^\text {th}$ dance is of type $C_ i$ and has a level of flair of $S_ i$.

It is guaranteed that for all positive integers $k \leq M$, there exists some $j$ such that $C_ j = k$.


On the first line, output a single integer $m$, the maximum number of dances she can perform.

On the second line, output $m$ integers $d_1, d_2, \dots , d_ m$ ($1 \leq d_ i \leq N$; $d_ i < d_{i+1}$ for all positive integers $i < m$), denoting the dances Yona should perform. In particular, the $i^\text {th}$ dance Yona should perform is the ${d_ i}^\text {th}$ one.

If there are multiple correct answers, you can output any of them.

Sample Input 1 Sample Output 1
7 3
1 4
2 2
1 6
1 3
2 5
2 8
3 7
2 4 5 7
Sample Input 2 Sample Output 2
10 5
1 5
2 5
3 5
4 5
5 5
1 11
1 12
1 13
1 14
1 15
4 7