Submission #638237

#	Time	Username	Problem	Language	Result	Execution time	Memory
638237		bonk	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	247 ms	19912 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, d, m; cin >> n >> d >> m;
    vector<int>freq[n + 1];

    for(int i = 1; i <= m; i++){
        int x; cin >> x;
        freq[x].push_back(i);
    }

    int l = 1, r = m;
    int ans = m;
    
    while(l <= r){
        int mid = (l + r)/2;
        queue<int>q;
        bool ok = true;

        for(int i = 1; i <= n; i++){
            if(!ok) break;
            for(int j = 0; j < freq[i].size(); j++) q.push(i);
            for(int j = 0; j < mid; j++){
                if(q.empty()) break;
                if(q.front() + d < i){
                    ok = false;
                    break;
                }
                q.pop();
            }
        }

        ok &= (q.empty());

        if(ok){
            ans = mid;
            r = mid - 1;
        } else{
            l = mid + 1;
        }
    }

    queue<int>q;
    vector<int>sv[n + 1];

    for(int i = 1; i <= n; i++){
        for(auto &x: freq[i]) q.push(x);
        for(int j = 0; j < ans; j++){
            if(q.empty()) break;
            sv[i].push_back(q.front()); q.pop();
        }
    }

    cout << ans << '\n';
    for(int i = 1; i <= n; i++){
        for(auto &x: sv[i]) cout << x << " ";
        cout << 0;
        if(i < n) cout << '\n';
    }

    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:25:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |             for(int j = 0; j < freq[i].size(); j++) q.push(i);
      |                            ~~^~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100