CF1814C.Search in Parallel
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Suppose you have n boxes. The i -th box contains infinitely many balls of color i . Sometimes you need to get a ball with some specific color; but you're too lazy to do it yourself.
You have bought two robots to retrieve the balls for you. Now you have to program them. In order to program the robots, you have to construct two lists [a1,a2,…,ak] and [b1,b2,…,bn−k] , where the list a represents the boxes assigned to the first robot, and the list b represents the boxes assigned to the second robot. Every integer from 1 to n must be present in exactly one of these lists.
When you request a ball with color x , the robots work as follows. Each robot looks through the boxes that were assigned to that robot, in the order they appear in the list. The first robot spends s1 seconds analyzing the contents of a box; the second robot spends s2 . As soon as one of the robots finds the box with balls of color x (and analyzes its contents), the search ends. The search time is the number of seconds from the beginning of the search until one of the robots finishes analyzing the contents of the x -th box. If a robot analyzes the contents of all boxes assigned to it, it stops searching.
For example, suppose s1=2 , s2=3 , a=[4,1,5,3,7] , b=[2,6] . If you request a ball with color 3 , the following happens:
- initially, the first robot starts analyzing the box 4 , and the second robot starts analyzing the box 2 ;
- at the end of the 2 -nd second, the first robot finishes analyzing the box 4 . It is not the box you need, so the robot continues with the box 1 ;
- at the end of the 3 -rd second, the second robot finishes analyzing the box 2 . It is not the box you need, so the robot continues with the box 6 ;
- at the end of the 4 -th second, the first robot finishes analyzing the box 1 . It is not the box you need, so the robot continues with the box 5 ;
- at the end of the 6 -th second, the first robot finishes analyzing the box 5 . It is not the box you need, so the robot continues with the box 3 . At the same time, the second robot finishes analyzing the box 6 . It is not the box you need, and the second robot has analyzed all the boxes in its list, so that robot stops searching;
- at the end of the 8 -th second, the first robot finishes analyzing the box 3 . It is the box you need, so the search ends;
- so, the search time is 8 seconds.
You know that you are going to request a ball of color 1 r1 times, a ball of color 2 r2 times, and so on. You want to construct the lists a and b for the robots in such a way that the total search time over all requests is the minimum possible.
输入格式
The first line contains one integer t ( 1≤t≤104 ) — the number of test cases.
Each test case consists of two lines:
- the first line contains three integers n , s1 , s2 ( 2≤n≤2⋅105 ; 1≤s1,s2≤10 );
- the second line contains n integers r1,r2,…,rn ( 1≤ri≤106 ).
Additional constraint on the input: the sum of n over all test cases does not exceed 2⋅105 .
输出格式
For each test case, print two lines. The first line should contain the list a , the second line — the list b . Each list has to be printed as follows: first, print the number of elements in it, and then the elements themselves.
If there are multiple answers, you may print any of them.
输入输出样例
输入#1
3 7 3 1 8 6 4 4 4 1 7 5 1 10 1 1 1 1 1 8 1 1 4 5 6 8 1 7 3 2
输出#1
2 5 6 5 1 7 2 4 3 5 4 3 5 2 1 0 4 4 2 7 5 4 6 3 1 8