Monk And IQ
Practice
4 (74 votes)
Approved
Easy
Open
Priority queue
Problem
59% Success 7242 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

Monk and his P-1 friends recently joined a college. He finds that N students have already applied for different courses before him. Courses are assigned numbers from 1 to C. He and his friends will follow the following conditions when choosing courses:-
They will choose the course i (1 <= i <= C), for which the value of z is minimum. Here, z = x*c where c is the number of students already enrolled in the course i and x is the sum of IQ of the last two students who enrolled in that course. If a single student has applied for a course, then the value of x will be that student's IQ. If no student has enrolled for that course, then value of x will be 0. If the value of z is same for two courses, then they will choose the course with the minimum course number. You need to find which courses Monk and his friends should take after following the above conditions.
Note: Each of them will choose their courses, one at a time. Monk will choose his course first followed by his friends.

Input:
The first line contains the numbers C, P and N where C denotes the number of courses in that college, P denotes Monk and his friends and N denotes the number of students who have already applied for the courses.
The next line consists of N space separated integers Y[i] which denotes the IQ of the ith student. Here, the ith student chooses the ith course.
The next line consists of P space separated integers X[i] which denotes the IQ of Monk and his friends.

Output:
Print P space separated integers in a line which denotes the course number which Monk and his friends have applied for.

Constraints:
1 <= C <= 100000
1 <= P <= 100000
1 <= N <= C
1 <= Y[i],X[i] <= 100000

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
155 votes
Tags:
ApprovedEasyHeapsOpenPriority queueTrees
Points:30
14 votes
Tags:
AlgorithmsBit ManipulationData StructuresMathPriority queueTrees