A13031. Show Must Go On
编程题
普及/提高-
知识点
题目描述
The first line contains one integer $t$ ( $1 \le t \le 10^5$ ) — the number of test cases in the input. Then the test cases follow.
Each test case begins with a line containing three integers $n$ , $k$ and $m$ ( $1 \le n \le 10^6$ , $1 \le k \le 10^{18}$ , $1 \le m \le 10^6$ ) — the total number of dancers, the maximum acceptable awkwardness of a set of dancers and the maximum number of concerts, respectively.
The following line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^{12}$ ), where $a_i$ is the awkwardness of the $i$ -th dancer.
The sum of the values of $n$ over all test cases in the input does not exceed $10^6$ . Similarly, the sum of the values of $m$ over all test cases in the input does not exceed $10^6$ .
Each test case begins with a line containing three integers $n$ , $k$ and $m$ ( $1 \le n \le 10^6$ , $1 \le k \le 10^{18}$ , $1 \le m \le 10^6$ ) — the total number of dancers, the maximum acceptable awkwardness of a set of dancers and the maximum number of concerts, respectively.
The following line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^{12}$ ), where $a_i$ is the awkwardness of the $i$ -th dancer.
The sum of the values of $n$ over all test cases in the input does not exceed $10^6$ . Similarly, the sum of the values of $m$ over all test cases in the input does not exceed $10^6$ .
输入格式
Print the answers to all test cases in the input.
If the troupe cannot give concerts at all, then simply print one line "0". In this case, you should not print anything else.
If the troupe gives a positive number of concerts $r$ ( $r$ is equal to the minimum of $m$ and the total number of valid sets), then first print the value of $r$ , then $r$ lines: the $j$ -th line should contain two integers $s_j$ and $t_j$ — the number of dancers in the $j$ -th concert and the total awkwardness of the dancers performing in the $j$ -th concert. Complete the output to a test case with a line that describes the last set: print exactly $s_r$ distinct integers from $1$ to $n$ — the numbers of the dancers who will perform at the $r$ -th (last) concert, in any order. If there are several answers, print any of them.
If the troupe cannot give concerts at all, then simply print one line "0". In this case, you should not print anything else.
If the troupe gives a positive number of concerts $r$ ( $r$ is equal to the minimum of $m$ and the total number of valid sets), then first print the value of $r$ , then $r$ lines: the $j$ -th line should contain two integers $s_j$ and $t_j$ — the number of dancers in the $j$ -th concert and the total awkwardness of the dancers performing in the $j$ -th concert. Complete the output to a test case with a line that describes the last set: print exactly $s_r$ distinct integers from $1$ to $n$ — the numbers of the dancers who will perform at the $r$ -th (last) concert, in any order. If there are several answers, print any of them.
输出格式
无
输入输出样例
输入 #1
3 7 13 10 3 1 5 1 8 2 13 2 10 1 12 12 3 32 100000 2 1 5
输出 #1
10 5 12 4 7 4 9 4 10 4 11 4 11 4 12 4 13 3 4 3 5 2 4 1 0 7 3 8 2 3 2 6 2 7 1 1 1 2 1 5 3