In this HackerEarth Monk And IQ problem solution 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 the value of x will be 0. If the value of z is the 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.


HackerEarth Monk And IQ problem solution


HackerEarth Monk And IQ problem solution.

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
#define mk make_pair
ll power(ll a, ll b) {
ll x = 1, y = a;
    while(b > 0) {
        if(b%2 == 1) {
            x=(x*y);
            if(x>mod) x%=mod;
        }
        y = (y*y);
        if(y>mod) y%=mod;
        b /= 2;
    }
    return x;
}
#define P pair<ll, int>
priority_queue< P, vector<P>, greater<P> > q;
ll a[100002];
int ans[100002];
vector<ll>price[100002];
int main()
{
    int c,n,k,i,s,l;
    cin>>c>>n>>k;
    for(i = 0; i < k; i++) {
        cin>>a[i];
        q.push(make_pair(a[i],i));
        price[i].push_back(a[i]);
    }
    for(i = k; i < c; i++) {
        q.push(make_pair(0,i));
    }
    for(i = 0; i < n; i++) {
        cin>>a[i];
    }
    pair<ll,int>z;
    for(i = 0; i < n; i++) {
        z = q.top();
        if(price[z.second].size() == 0) {
            price[z.second].push_back(a[i]);
            z.first += a[i];
            ans[i] = z.second;
            q.pop();
            q.push(z);
        }
        else if(price[z.second].size() == 1) {
            z.first = (z.first+a[i])*2;
            price[z.second].push_back(a[i]);
            ans[i] = z.second;
            q.pop();
            q.push(z);
        }
        else if(price[z.second].size() >= 2) {
            l = price[z.second].size();
            z.first = (price[z.second][l-1]+a[i]);
            price[z.second].push_back(a[i]);
            ans[i] = z.second;
            z.first *= (l+1);
            q.pop();
            q.push(z);
        }
    }
    for(i = 0; i < n; i++) {
        cout<<ans[i]+1<<" ";
    }
    return 0;
}