A183290.分类入围

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:256MB

题目描述

有 nn 个报名项目。每个项目都有互不相同的编号 idiid_i,以及类别编号 cic_i、得分 sis_i 和用时 tit_i。

每个类别最多选出 kk 个项目入围。各类别独立选择,顺序按以下规则确定:

  1. 先比较得分,得分高的在前。
  2. 得分相同时,才比较用时,用时少的在前。
  3. 得分和用时都相同时,才比较项目编号,编号小的在前。

每类取排在最前面的 kk 个项目;不足 kk 个时全部入围。最终将所有入围项目的编号从小到大输出。项目编号的大小与输入顺序没有关系。

输入格式

第一行包含两个整数 nn、kk,分别表示项目数量和每个类别的入围数量上限。

接下来 nn 行,每行包含四个整数 idiid_i、cic_i、sis_i、tit_i,分别表示第 ii 个输入项目的编号、类别编号、得分和用时。

输出格式

第一行输出入围项目总数。第二行按编号从小到大的顺序输出所有入围项目编号,相邻编号之间用一个空格分隔。

输入输出样例

  • 输入#1

    6 2
    40 1 90 5
    10 1 90 5
    30 1 90 4
    25 2 80 2
    5 2 85 9
    50 3 0 0
    

    输出#1

    5
    5 10 25 30 50
    
  • 输入#2

    4 1
    99 7 10 1
    2 7 11 8
    8 9 5 3
    1 9 5 3
    

    输出#2

    2
    1 2
    

说明/提示

样例 #1 解释

类别 11 的选择顺序为编号 3030、1010、4040:3030 的用时更少;1010 与 4040 得分和用时相同,按编号决定先后。该类入围 3030、1010。

类别 22 只有两个项目,类别 33 只有一个项目,均全部入围。将五个入围编号重新按从小到大排列,得到 5 10 25 30 50。

数据范围

  • 1≤n≤1051\le n\le10^5,1≤k≤51\le k\le5。
  • 1≤idi,ci≤1091\le id_i,c_i\le10^9,所有 idiid_i 互不相同。
  • 0≤si,ti≤1090\le s_i,t_i\le10^9。

输入解题思路,AI测评打分。不知道怎么写?

首页