제출 #476433

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
476433		horsefeedapples	Job Scheduling (CEOI12_jobs)	C++11	0 / 100	684 ms	20140 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);

    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);
        int sz = ans[currDay].size();
        if(sz>=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;
}

• Subtask 1: 0 / 100