Submission #566585

#	Time	Username	Problem	Language	Result	Execution time	Memory
566585		zuhaib786	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	449 ms	9544 KiB

jobs

#include<bits/stdc++.h>
using namespace std;
using lli = long long int;
using pii = pair<lli, lli>;
using vc = vector<lli>;

#define FOR(i, n) for(int i= 0; i< n; i++)
#define ROF(i, n) for(int i = n - 1; i>= 0; i--)
#define ff first
#define ss second
const int maxN  = 1e5 + 5;
pii arr[maxN];
map<lli, vector<int>>mp;
vector<vector<int>>simulate(lli mid, lli n, lli m, lli d)
{
    multiset<pii>s;
    vector<vector<int>>v;
    // cout<<"MId = "<<mid<<"\n";
    FOR(i, n)
    {
        // cout<<s.size()<<'\n';
        if(mp.count(i + 1))
        {
            // printVec(mp[i + 1]);
            for(auto x : mp[i + 1])
            {
                s.insert({i + 1, x});
            }
        }
        if(s.size() <= mid)
        {
            vector<int>temp;
            for(auto x: s)
            {
                temp.push_back(x .second + 1);
            }   
            temp.push_back(0);
            v.push_back(temp);
            s = multiset<pii>();
        }
        else
        {
            int k = mid;
            vector<int>temp;
            while(k-- )
            {
                temp.push_back((*s.begin()).ss + 1);
                s.erase(s.find(*s.begin()));
            }
            temp.push_back(0);
            v.push_back(temp);
        }
    }
    return v;
}
bool Poss(lli mid, lli n, lli m, lli d)
{
    multiset<lli>s;
    // cout<<"MId = "<<mid<<"\n";
    FOR(i, n)
    {
        // cout<<s.size()<<'\n';
        if(mp.count(i + 1))
        {
            // printVec(mp[i + 1]);
            for(auto x : mp[i + 1])
            {
                s.insert(i + 1);
            }
        }
        
        if(s.size()!= 0 &&*s.begin() + d < i + 1)
        {
            // cout<<*s.begin()<<" " << i + 1<<" "<<mid<<"\n";
            return false;
        }
        if(s.size() <= mid)
        {
            s = multiset<lli>();
        }
        else
        {
            int k = mid;
            while(k-- )
            {
                s.erase(s.find(*s.begin()));
            }
        }
    }
    return s.size() == 0;
}
int main()
{
    int n, m, d;
    cin>>n>>d>>m;
    FOR(i, m)
    {
        cin>>arr[i].ff;
        arr[i].ss = i;
        mp[arr[i].ff].push_back(i);
    }
    sort(arr, arr + n);
    lli left = 1;
    lli right = m;
    lli ans = m;
    while(left <= right)
    {
        lli mid = left + (right - left )/2;
        if(Poss(mid, n, m, d))
        {
            ans = mid;
            right = mid - 1;   
        }
        else
        {
            left = mid + 1;
        }
    }
    cout<<ans<<'\n';
    vector<vector<int>>v = simulate(ans, n, m, d);
    for(auto x : v)
    {
        for(auto w: x)
        {
            cout<<w<<" ";
        }
        cout<<'\n';
    }
}

Compilation message (stderr)

jobs.cpp: In function 'std::vector<std::vector<int> > simulate(lli, lli, lli, lli)':
jobs.cpp:30:21: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'lli' {aka 'long long int'} [-Wsign-compare]
   30 |         if(s.size() <= mid)
      |            ~~~~~~~~~^~~~~~
jobs.cpp: In function 'bool Poss(lli, lli, lli, lli)':
jobs.cpp:66:22: warning: unused variable 'x' [-Wunused-variable]
   66 |             for(auto x : mp[i + 1])
      |                      ^
jobs.cpp:77:21: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'lli' {aka 'long long int'} [-Wsign-compare]
   77 |         if(s.size() <= mid)
      |            ~~~~~~~~~^~~~~~

• Subtask 1: 0 / 100