oj.uz

Submission #438303

# Submission time Handle Problem Language Result Execution time Memory
438303 2021-06-27T20:37:50 Z horsefeedapples Job Scheduling (CEOI12_jobs) C++17
100 / 100
 685 ms 20104 KB 
#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);
        if(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);
        if(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

jobs.cpp: In function 'int main()':
jobs.cpp:49:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |         if(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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 4664 KB Output is correct
2 Correct 63 ms 4664 KB Output is correct
3 Correct 64 ms 4572 KB Output is correct
4 Correct 62 ms 4784 KB Output is correct
5 Correct 65 ms 4580 KB Output is correct
6 Correct 65 ms 4724 KB Output is correct
7 Correct 63 ms 4584 KB Output is correct
8 Correct 63 ms 4696 KB Output is correct
9 Correct 210 ms 4832 KB Output is correct
10 Correct 212 ms 4780 KB Output is correct
11 Correct 62 ms 4468 KB Output is correct
12 Correct 116 ms 6428 KB Output is correct
13 Correct 173 ms 8968 KB Output is correct
14 Correct 261 ms 11048 KB Output is correct
15 Correct 287 ms 11976 KB Output is correct
16 Correct 375 ms 14108 KB Output is correct
17 Correct 453 ms 17980 KB Output is correct
18 Correct 482 ms 18516 KB Output is correct
19 Correct 685 ms 20104 KB Output is correct
20 Correct 439 ms 17984 KB Output is correct