oj.uz

Submission #1043805

# Submission time Handle Problem Language Result Execution time Memory
1043805 2024-08-04T18:47:33 Z dpsaveslives Job Scheduling (CEOI12_jobs) C++17
100 / 100
 189 ms 20076 KB 
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int MAXN = 1e5+10;
vector<int> sched[MAXN];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N,D,M; cin >> N >> D >> M;
    vector<pair<int,int>> times(M);
    for(int i = 0;i<M;++i){
        cin >> times[i].f;
        times[i].s = i+1;
    }
    sort(times.begin(),times.end());
    int lo = 1, hi = M; ++hi;
    while(lo < hi){
        int mid = lo+(hi-lo)/2;
        vector<int> machines(mid,0);
        bool good = true;
        for(int i = 0;i<times.size();++i){
            if(machines[i%mid]+1 > times[i].f+D){
                good = false;
                break;
            }
            machines[i%mid] = max(machines[i%mid]+1,times[i].f);
        }
        if(good){
            hi = mid;
        }
        else{
            lo = mid+1;
        }
    }
    cout << lo << "\n";
    vector<int> machines(lo,0);
    for(int i = 0;i<times.size();++i){
        machines[i%lo] = max(machines[i%lo]+1,times[i].f);
        //cout << machines[i%lo] << " " << times[i].f << "\n";
        sched[machines[i%lo]].push_back(times[i].s);
    }
    for(int i = 1;i<=N;++i){
        if(sched[i].size() == 0){
            cout << 0 << "\n";
            continue;
        }
        for(int j = 0;j<sched[i].size();++j){
            cout << sched[i][j] << " ";
        }
        cout << 0 << "\n";
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:22:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(int i = 0;i<times.size();++i){
      |                       ~^~~~~~~~~~~~~
jobs.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i = 0;i<times.size();++i){
      |                   ~^~~~~~~~~~~~~
jobs.cpp:48:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int j = 0;j<sched[i].size();++j){
      |                       ~^~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5016 KB Output is correct
2 Correct 13 ms 5016 KB Output is correct
3 Correct 13 ms 5016 KB Output is correct
4 Correct 14 ms 5044 KB Output is correct
5 Correct 14 ms 5016 KB Output is correct
6 Correct 14 ms 5016 KB Output is correct
7 Correct 14 ms 5016 KB Output is correct
8 Correct 13 ms 5016 KB Output is correct
9 Correct 21 ms 4756 KB Output is correct
10 Correct 25 ms 4760 KB Output is correct
11 Correct 19 ms 4500 KB Output is correct
12 Correct 37 ms 6540 KB Output is correct
13 Correct 57 ms 8972 KB Output is correct
14 Correct 77 ms 11296 KB Output is correct
15 Correct 92 ms 11900 KB Output is correct
16 Correct 116 ms 14264 KB Output is correct
17 Correct 134 ms 18168 KB Output is correct
18 Correct 173 ms 18520 KB Output is correct
19 Correct 189 ms 20076 KB Output is correct
20 Correct 138 ms 18188 KB Output is correct