Submission #1257331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257331		satyanshu	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	218 ms	30556 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 7;
bool bipartite;
const int MAXN = 200005;
ll fact[MAXN];
ll h, c, t;
const ll NEG_INF = -1e17 - 7;

vector<vector<int>> f(int machine_cnt, vector<pair<int,int>> &arrivals, int d, int n){
    int m = arrivals.size();  
    vector<vector<int>>schedule(n+1);
      
      int ptr = 0;

      for(int i=1;i<=n;i++){
        int cur_day_machine_used = 0;
        while(cur_day_machine_used < machine_cnt){
            if(ptr >= m) return schedule;
            if(arrivals[ptr].first > i){
                //it means cur job ka arrival cur day se baad ka hai 
                cur_day_machine_used = 0;
                break;
            }
            if(arrivals[ptr].first + d < i){
                return {};
            }
            cur_day_machine_used++;
            schedule[i].push_back(arrivals[ptr].second);
            ptr++;

            if(ptr == m) return schedule;
        }
      }

      return {};
}


void solve()
{
     int n, m, d;
     cin>>n>>d>>m;

     vector<int>jobs(m);
     vector<pair<int,int>>arrivals(m);
     for(int i=0;i<m;i++){
        cin>>jobs[i];
        arrivals[i] = {jobs[i], i+1};
     }

     sort(arrivals.begin(), arrivals.end());

     vector<vector<int>> res;
     int low = 0, high = m+1, ans = 0;
     while(low <= high){
        int mid = (low + high)/2;

        vector<vector<int>>temp = f(mid, arrivals, d, n);

        if(!temp.empty()){
            ans = mid;
            res = temp;
            high = mid - 1;
        }
        else{
            low = mid + 1;
        }
     }

     cout<<ans<<endl;
     for(int i=1;i<=n;i++){
        for(auto it: res[i]){
            cout<<it<<" ";
        }
        cout<<0<<endl;
     }

     return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

• Subtask 1: 100 / 100