luogu#P9925. [POI 2023/2024 R1] Zapobiegliwy student

[POI 2023/2024 R1] Zapobiegliwy student

题目背景

译自 XXXI Olimpiada Informatyczna - I etap Zapobiegliwy student

题目描述

考虑如下的一个简单问题:

你有 nn 个线段在数轴上,你要选出尽量多的线段,使它们两两不交。

我知道你一定会做,但你需要解决这个:

你有 nn 个线段在数轴上,你要选出尽量多的线段对 (ui,vi)i=1k(u_i,v_i)_{i=1}^k,即最大化 kk

满足 k+1k+1 个要求:

  • u1,u2,,uku_1,u_2,\cdots,u_k 两两不交。
  • v1,u2,u3,,ukv_1,u_2,u_3,\cdots,u_k 两两不交。
  • u1,v2,u3,u4,,uku_1,v_2,u_3,u_4,\cdots,u_k 两两不交。
  • \cdots
  • u1,u2,,uk1,vku_1,u_2,\cdots,u_{k-1},v_k 两两不交。

其中 i\forall iuiu_iviv_i 不能相同。

输入格式

第一行一个正整数 n(n2)n(n\geq2)

接下来 nn 行每行两个正整数 ai,bi(1ai<bi109)a_i,b_i(1\leq a_i<b_i\leq10^9),表示一个线段的两个端点。

两个线段 i,ji,j 不交当且仅当 biajb_i\leq a_jbjaib_j\leq a_i

输出格式

第一行一个正整数 kk

接下来 kk 行,每行两个正整数 ui,viu_i,v_i,表示一对线段的编号。

8
1 5
3 10
4 8
9 12
11 16
14 15
20 22
15 21

3
1 3
4 6
8 7

见附件
见附件
见附件
见附件

提示

如果你的第一行正确但是方案不对(可以不输出方案,此时不要有换行),你能得到 50%50\% 的分数。

如果你的方案合法并且第一行和答案相差不超过 11,你能得到 15%15\% 的分数。

子任务编号 限制 分值
1 n3000n\leq3000 40
2 n500000n\leq500000 60