#1877. (LIS, LDS) - Coordinates
(LIS, LDS) - Coordinates
(LIS, LDS) - Coordinates
题目描述
标题: (LIS, LDS) - Coordinates - Problem - QOJ.ac
#9635. (LIS, LDS) - Coordinates
题目描述
对于一个排列 p,按照以下方式定义 f(p):
- 对于排列中的一个元素 pi,令 ai 为以其结尾的最长上升子序列长度,bi 为以其开头的最长下降子序列长度,定义其坐标为有序二元组 (ai,bi)。
- f(p) 为 p 中所有元素的坐标构成的集合。
例如,f(1,2,5,4,3,6)={(1,1),(2,1),(3,1),(3,2),(3,3),(4,1)}。
给定正整数 n 和 n 个互不相同的有序二元组 (x1,y1),(x2,y2),…,(xn,yn),其中 xi,yi 均为不超过 n 的正整数。
构造一个长度最小的排列 p,使得 f(p) 包含所有 n 个给定的二元组,f(p) 可以包含 n 个给定的二元组以外的其他元素。
若有多个长度最小的排列,输出任意一个。可以证明,在给定条件下,总是存在一个长度不超过 3n 的排列。
若你输出的排列不是长度最小的排列,但是长度不超过给定参数 lim,也可获得部分分数。
输入格式
输入的第一行包含两个正整数 n,lim,分别表示二元组的数量和你构造的排列的长度上限。
接下来 n 行,每行包含两个正整数 xi,yi,表示 f(p) 必须包含 (xi,yi)。
输出格式
输出两行。第一行包含一个正整数 m,表示你构造的排列长度,你需要保证 n≤m≤lim。
第二行包含 m 个正整数,表示你构造的排列 p。
样例 1
input
2 6
2 1
1 2
output
3
2 1 3
样例 2
input
2 6
2 2
2 1
output
3
1 3 2
样例 3
input
3 9
1 1
2 1
3 3
output
5
1 4 5 3 2
样例 4
input
4 12
3 1
2 4
1 4
2 3
output
7
4 6 3 5 2 1 7
样例 5
input
6 18
1 1
4 2
1 4
2 4
1 5
4 1
output
9
5 4 6 3 2 7 9 1 8
样例 6
input
8 24
1 3
3 1
2 5
2 4
5 3
3 2
1 1
4 2
output
10
5 9 8 1 2 4 7 10 6 3
样例 7
input
10 30
3 3
5 10
5 8
8 7
2 6
3 4
2 2
7 3
4 4
10 10
output
22
2 9 4 6 12 15 16 18 20 21 22 14 13 11 19 10 8 7 5 17 3 1
数据范围
对于所有数据,保证 1≤n≤5000, 3n≤lim≤15000, 1≤xi,yi≤n。
本题共 6 个子任务:
子任务编号 分值 额外限制 1 5 n≤4 2 15 n≤100,lim≥n2 3 25 n≤300 4 25 长度最小的排列恰好为 n 5 10 (xn,yn)=(n,n) 6 20 无额外限制
对于每个测试点,若你成功构造了长度不超过 lim 的排列,可以获得 40% 的分数;若你成功构造了长度最小的排列,可以获得 100% 的分数。对于每个子任务,你的得分为其所有测试点得分的最小值。
下发文件中的 chk.cpp 可以用于检验你的输出。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2 6
2 1
1 2
3
2 1 3
样例 2
2 6
2 2
2 1
3
1 3 2