Submission #438302

#	Time	Username	Problem	Language	Result	Execution time	Memory
438302		horsefeedapples	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	682 ms	21660 KiB

jobs

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MXN = 1e5+5;

int N, D, M;
vector<pair<int,int>> jobs; // day, index
vector<int> ans[MXN];

bool check(int machines){
    // Filled[i] represents how many tasks are processed on day i
    vector<int> filled(MXN, 0);
    int currDay = 0;
    for(int i=0; i<M; i++){
        currDay = max(currDay, jobs[i].first);
        while(filled[currDay]>=machines) currDay++; // try if(filled[head]>=x)
        if(currDay>jobs[i].first+D) return false;
        filled[currDay]++;
    }
    return true;
}

int firstTrue(int lo, int hi) {
	for (hi ++; lo < hi; ) {
		int mid = lo+(hi-lo)/2;
		if (check(mid)) hi = mid;
		else lo = mid+1;
	}
	return lo;
}

int main(){
    cin>>N>>D>>M;
    for(int i=0; i<M; i++){
        int x; cin>>x;
        jobs.push_back({x, i+1});
    }
    sort(jobs.begin(), jobs.end());

    int numMachines = firstTrue(0, MXN); 

    cout<<numMachines<<endl;
    
    int currDay = 0;
    for(int i=0; i<M; i++){
        currDay = max(currDay, jobs[i].first);
        while(ans[currDay].size()>=numMachines) currDay++;
        ans[currDay].push_back(jobs[i].second);
    }

    for(int i=1; i<=N; i++){
        for(int j=0; j<ans[i].size(); j++){
            cout<<ans[i][j]<<" ";
        }
        cout<<0<<endl;
    }
    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:49:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |         while(ans[currDay].size()>=numMachines) currDay++;
      |               ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
jobs.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int j=0; j<ans[i].size(); j++){
      |                      ~^~~~~~~~~~~~~~

• Subtask 1: 100 / 100