Dirty Deeds Done Dirt Cheap
题意翻译
## 题目描述
有 $n$ 个整数对 $(a_1, b_1), (a_2, b_2), \cdots, (a_n, b_n)$. 保证 $a_1, b_1, a_2, b_2, \cdots, a_n, b_n$ 两两不相等, 并且均在区间 $[1, 2 \cdot n]$ 内.
好序列的定义:
对于一个序列 $x_1, x_2, \cdots, x_{2k}$, 满足
- $x_1 < x_2 > x_3 < \cdots < x_{2k - 2} > x_{2k - 1} < x_{2k}$ 或
- $x_1 > x_2 < x_3 > \cdots > x_{2k - 2} < x_{2k - 1} > x_{2k}$.
求一个序列 $i_1, i_2, \cdots, i_t$ 满足 $a_{i_1}, b_{i_1}, a_{i_2}, b_{i_2}, \cdots, a_{i_t}, b_{i_t}$ 是好序列.
输出 $t$ 的最大值以及对应的序列 $i_1, i_2, \cdots, i_t$.
## 输入输出格式
### 输入格式
第一行包含一个整数 $n$, 即数对的个数.
后面 $n$ 行为数对, 每行包含一个数对 $(a_i, b_i)$.
### 输出格式
第一行输出 $t$, 即所求序列长度.
接着输出满足题意的序列 $i_1, i_2, \cdots, i_t$.
## 说明
### 数据范围
$2 \leq n \leq 3 \cdot 10^5$
$1 \leq a_i, b_i \leq 2 \cdot n$
并且所有 $a_i, b_i$ 两两不相等.
### 样例解释
样例 1: $1 < 7 > 3 < 5 > 2 < 10$.
样例 2: $6 > 1 < 3 > 2 < 5 > 4$.
题目描述
You are given $ n $ pairs of integers $ (a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n) $ . All of the integers in the pairs are distinct and are in the range from $ 1 $ to $ 2 \cdot n $ inclusive.
Let's call a sequence of integers $ x_1, x_2, \ldots, x_{2k} $ good if either
- $ x_1 < x_2 > x_3 < \ldots < x_{2k-2} > x_{2k-1} < x_{2k} $ , or
- $ x_1 > x_2 < x_3 > \ldots > x_{2k-2} < x_{2k-1} > x_{2k} $ .
You need to choose a subset of distinct indices $ i_1, i_2, \ldots, i_t $ and their order in a way that if you write down all numbers from the pairs in a single sequence (the sequence would be $ a_{i_1}, b_{i_1}, a_{i_2}, b_{i_2}, \ldots, a_{i_t}, b_{i_t} $ ), this sequence is good.
What is the largest subset of indices you can choose? You also need to construct the corresponding index sequence $ i_1, i_2, \ldots, i_t $ .
输入输出格式
输入格式
The first line contains single integer $ n $ ( $ 2 \leq n \leq 3 \cdot 10^5 $ ) — the number of pairs.
Each of the next $ n $ lines contain two numbers — $ a_i $ and $ b_i $ ( $ 1 \le a_i, b_i \le 2 \cdot n $ ) — the elements of the pairs.
It is guaranteed that all integers in the pairs are distinct, that is, every integer from $ 1 $ to $ 2 \cdot n $ is mentioned exactly once.
输出格式
In the first line print a single integer $ t $ — the number of pairs in the answer.
Then print $ t $ distinct integers $ i_1, i_2, \ldots, i_t $ — the indexes of pairs in the corresponding order.
输入输出样例
输入样例 #1
5
1 7
6 4
2 10
9 8
3 5
输出样例 #1
3
1 5 3
输入样例 #2
3
5 4
3 2
6 1
输出样例 #2
3
3 2 1
说明
The final sequence in the first example is $ 1 < 7 > 3 < 5 > 2 < 10 $ .
The final sequence in the second example is $ 6 > 1 < 3 > 2 < 5 > 4 $ .