Submission #638236

#	Time	Username	Problem	Language	Result	Execution time	Memory
638236		bonk	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	241 ms	23224 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(auto &x: freq[i]) q.push(i);
            for(int j = 0; j < mid; j++){
                if(q.empty()) break;
                if(q.front() + d < i){
                    ok = false;
                    break;
                }
                q.pop();
            }
        }

        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();
        }

        sv[i].push_back(0);
    }

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

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:25:23: warning: unused variable 'x' [-Wunused-variable]
   25 |             for(auto &x: freq[i]) q.push(i);
      |                       ^

• Subtask 1: 0 / 100