#C. [POI 2023/2024 R1] Zapobiegliwy student

    Type: RemoteJudge 500ms 256MiB

[POI 2023/2024 R1] Zapobiegliwy student

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

译自 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

周四下午训练

Not Attended
Status
Done
Rule
IOI
Problem
5
Start at
2025-2-20 8:00
End at
2025-2-20 17:00
Duration
9 hour(s)
Host
Partic.
6