[POI 2023/2024 R1] Zapobiegliwy student

Luogu
IDLGP9925
Time500ms
Memory256MB
DifficultyP6
贪心POI(波兰)2023Special Judge构造
考虑如下的一个简单问题: > 你有 $n$ 个线段在数轴上,你要选出尽量多的线段,使它们两两不交。 我知道你一定会做,但你需要解决这个: 你有 $n$ 个线段在数轴上,你要选出尽量多的线段对 $(u_i,v_i)_{i=1}^k$,即最大化 $k$。 满足 $k+1$ 个要求: - $u_1,u_2,\cdots,u_k$ 两两不交。 - $v_1,u_2,u_3,\cdots,u_k$ 两两不交。 - $u_1,v_2,u_3,u_4,\cdots,u_k$ 两两不交。 - $\cdots$ - $u_1,u_2,\cdots,u_{k-1},v_k$ 两两不交。 其中 $\forall i$,$u_i$ 与 $v_i$ 不能相同。 ## Input 第一行一个正整数 $n(n\geq2)$。 接下来 $n$ 行每行两个正整数 $a_i,b_i(1\leq a_i<b_i\leq10^9)$,表示一个线段的两个端点。 两个线段 $i,j$ 不交当且仅当 $b_i\leq a_j$ 或 $b_j\leq a_i$。 ## Output 第一行一个正整数 $k$。 接下来 $k$ 行,每行两个正整数 $u_i,v_i$,表示一对线段的编号。 [samples] ## Background 译自 [XXXI Olimpiada Informatyczna - I etap](https://sio2.mimuw.edu.pl/c/oi31-1/dashboard/) [Zapobiegliwy student](https://sio2.mimuw.edu.pl/c/oi31-1/p/zap/)。 ## Note 如果你的第一行正确但是方案不对(可以不输出方案,此时不要有换行),你能得到 $50\%$ 的分数。 如果你的方案合法并且第一行和答案相差不超过 $1$,你能得到 $15\%$ 的分数。 | 子任务编号 | 限制 | 分值 | | :----------: | :----------: | :----------: | | 1 | $n\leq3000$ | 40 | | 2 | $n\leq500000$ | 60 |
Samples
Input #1
8
1 5
3 10
4 8
9 12
11 16
14 15
20 22
15 21
Output #1
3
1 3
4 6
8 7
Input #2
见附件
Output #2
见附件
Input #3
见附件
Output #3
见附件
API Response (JSON)
{
  "problem": {
    "name": "[POI 2023/2024 R1] Zapobiegliwy student",
    "description": {
      "content": "考虑如下的一个简单问题: > 你有 $n$ 个线段在数轴上,你要选出尽量多的线段,使它们两两不交。 我知道你一定会做,但你需要解决这个: 你有 $n$ 个线段在数轴上,你要选出尽量多的线段对 $(u_i,v_i)_{i=1}^k$,即最大化 $k$。 满足 $k+1$ 个要求: - $u_1,u_2,\\cdots,u_k$ 两两不交。 - $v_1,u_2,u_3,\\cdots,u_k$",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 500,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9925"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "考虑如下的一个简单问题:\n\n> 你有 $n$ 个线段在数轴上,你要选出尽量多的线段,使它们两两不交。\n\n我知道你一定会做,但你需要解决这个:\n\n你有 $n$ 个线段在数轴上,你要选出尽量多的线段对 $(u_i,v_i)_{i=1}^k$,即最大化 $k$。\n\n满足 $k+1$ 个要求:\n\n- $u_1,u_2,\\cdots,u_k$ 两两不交。\n- $v_1,u_2,u_3,\\cdots,u_k$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments