Submission #751845

#	Time	Username	Problem	Language	Result	Execution time	Memory
751845		ndh990	Job Scheduling (CEOI12_jobs)	C++11	80 / 100	509 ms	45432 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> pairs;
using vi = vector<ll>;
const ll MOD = 1e9+7;
#define mp make_pair
 ll n,d,m;
pair<bool, vector<vi>> isFeasible(const vector<pairs> &jobs, int machineCount) {
        vector<vi> schedule(n);
        ll reqNum = 0;
for (ll day = 1; day <= n; day++) {
    for (ll j = 0; j < machineCount; j++) {
            if(jobs[reqNum].first>day)
        {
            break;
        }
        if(jobs[reqNum].first+d>=day)
        {
            schedule[day-1].push_back(jobs[reqNum++].second);
        }
        else return mp(false, schedule);
        if (reqNum == m) return mp(true, schedule);
    }
}
return mp(false, schedule);
}
int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> d >> m;
    vector <pairs> jobs(m);
    for(int i=0;i<m;i++)
    {
        cin >> jobs[i].first;
        jobs[i].second=i+1;
    }
    sort(jobs.begin(),jobs.end());
    int l =1;
    int r =m;
    vector<vi> result;
    while (l < r) {
		int machineNum = l+(r - l) / 2;
		pair<bool, vector<vi>> curResult = isFeasible(jobs, machineNum);
		if (curResult.first) {
			r = machineNum;
			result = curResult.second;
		}
		else
			l = machineNum + 1;
    }
    cout << l << "\n";
	for (int i = 0; i < n; i++) {
		for (auto &idx : result[i]) cout << idx << " ";
		cout << 0 << "\n";
	}







}

• Subtask 1: 80 / 100