‹ 上一题 下一题 ›

s09185. 反悔实况 未做

1000 ms 256 MB 测试点 10 通过率 33% S-06·贪心进阶与反悔贪心反悔贪心

题目描述

排程台用一套固定的反悔流程安排 个任务:每个时段恰好完成一个任务,任务按给定顺序逐个处理,第 个任务须在时段 或更早完成(保证 ),报酬为 。

流程规则如下,不可更改:

  1. 任务 先直接进入当前保留集合;
  2. 若保留集合中的任务数超过 :发生一次反悔——从保留集合中退掉报酬最低的任务;报酬相同时退编号最小的;
  3. 否则本步无反悔。

你的任务是逐步输出流程实况。

输入格式

第一行一个整数 。

接下来 行,第 行两个整数 ,保证 。

输出格式

共 行。处理完第 个任务后输出两行:

  • 第一行:当前保留集合中的任务编号,按编号从小到大以空格分隔;若集合为空,输出 -;
  • 第二行:本步发生反悔输出 Y,否则输出 N。

样例 1

样例

输入
5
1 9
2 5
2 6
3 7
3 2
输出
1
N
1 2
N
1 3
Y
1 3 4
N
1 3 4
Y

第 步保留数 超过 ,退掉报酬最低的编号 (报酬 ),换入编号 ;第 步保留数 超过 ,报酬最低者是刚入选的编号 (报酬 ),刚入选就被退掉。

样例 2

第 步保留数 超过 ,报酬最低者是编号 (报酬 )——虽然是老任务,一样退掉。

数据范围

;;。

输入
输出

            
答案