Submission #740179

#	Time	Username	Problem	Language	Result	Execution time	Memory
740179		Unforgettablepl	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	369 ms	23464 KiB

jobs

/*
ID: samikgo1
TASK:
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
//#define f first
//#define s second
//#define x first
//#define y second
const int INF = INT32_MAX;
vector<pair<int,int>> jobs;
int n,d,m;

bool check(int machines, bool print){
    // machines is the amount of machines we have
    if(machines==0){return false;}
    int day = 1;
    int curr = 0;
    vector<vector<int>> schedule(n);
    for(auto&job:jobs){
        while(job.first>day){
            curr = 0;
            day++;
        }
        if(day-job.first>d){
            return false;
        }
        curr++;
        schedule[day-1].emplace_back(job.second);
        if(curr == machines){
            day++;
            curr = 0;
        }
    }
    if(print){
        cout << machines << '\n';
        for(auto&i:schedule){
            for(int&j:i){
                cout << j << ' ';
            }
            cout << "0\n";
        }
    }
    return true;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("measurement.in","r",stdin);
//    freopen("measurement.out","w",stdout);
    cin >> n >> d >> m;
    jobs.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> jobs[i].first;
        jobs[i].second = i+1;
    }
    sort(all(jobs));
    int l = 1;
    int r = 1000000;
    int ans = 1000000;
    while(l<=r){
        int mid = (l+r)/2;
        if(check(mid,false)){
            ans = min(ans,mid);
            r = mid-1;
        } else {
            l = mid+1;
        }
    }
    check(ans,true);
}

• Subtask 1: 100 / 100