Submission #476434

# Submission time Handle Problem Language Result Execution time Memory
476434 2021-09-26T19:49:35 Z horsefeedapples Job Scheduling (CEOI12_jobs) C++11
100 / 100
603 ms 20268 KB
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define f first
#define s second

const int MX = 1e5+5;

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

bool check(int machines){
    int currDay = v[0].f;
    vector<int> filled(MX, 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, MX);

    cout<<req<<endl;

    vector<int> ans[MX];

    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;
    }
}
# Verdict Execution time Memory Grader output
1 Correct 57 ms 4680 KB Output is correct
2 Correct 57 ms 4600 KB Output is correct
3 Correct 53 ms 4592 KB Output is correct
4 Correct 54 ms 4664 KB Output is correct
5 Correct 55 ms 4568 KB Output is correct
6 Correct 54 ms 4680 KB Output is correct
7 Correct 57 ms 4596 KB Output is correct
8 Correct 57 ms 4620 KB Output is correct
9 Correct 192 ms 4828 KB Output is correct
10 Correct 175 ms 4964 KB Output is correct
11 Correct 61 ms 4436 KB Output is correct
12 Correct 106 ms 6448 KB Output is correct
13 Correct 160 ms 9112 KB Output is correct
14 Correct 240 ms 11272 KB Output is correct
15 Correct 253 ms 11864 KB Output is correct
16 Correct 368 ms 14236 KB Output is correct
17 Correct 401 ms 18100 KB Output is correct
18 Correct 445 ms 18440 KB Output is correct
19 Correct 603 ms 20268 KB Output is correct
20 Correct 418 ms 18120 KB Output is correct