Submission #476432

#	Time	Username	Problem	Language	Result	Execution time	Memory
476432		horsefeedapples	Job Scheduling (CEOI12_jobs)	C++11	0 / 100	715 ms	23484 KiB

jobs

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

#define f first
#define s second

int n, d, m;
vector<pair<int,int>> v;

bool check(int machines){
    int currDay = v[0].f;
    vector<int> filled(1e5+5, 0);
    bool possible = true;

    for(int i=0; i<m; i++){
        currDay = max(currDay, v[i].f);
        if(filled[currDay]>=machines) currDay++;
        if(currDay-d>v[i].f) return false;
        filled[currDay]++;
    }

    return true;
}

int firstTrue(int lo, int hi) {
	hi++;
	while (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;
        v.push_back({x, i});
    }
    sort(begin(v), end(v));

    int req = firstTrue(1, 1e9);

    cout<<req;

    vector<int> ans[(int) (1e5+5)];

    int currDay = 0;
    for(int i=0; i<m; i++){
        currDay = max(currDay, v[i].f);
        if(ans[currDay].size()>=req){
            currDay++;
        }
        ans[currDay].push_back(v[i].s);
    }

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

Compilation message (stderr)

jobs.cpp: In function 'bool check(int)':
jobs.cpp:15:10: warning: unused variable 'possible' [-Wunused-variable]
   15 |     bool possible = true;
      |          ^~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:57:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |         if(ans[currDay].size()>=req){
      |            ~~~~~~~~~~~~~~~~~~~^~~~~

• Subtask 1: 0 / 100