Submission #973195

#	Time	Username	Problem	Language	Result	Execution time	Memory
973195		njoop	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	145 ms	13652 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

int n, d, m, in, l=0, r=1e9, mid;
vector<int> t[100010];

bool solve(int num) {
    queue<int> q;
    for(int i=1; i<=n; i++) {
        for(int j: t[i]) q.push(i);
        for(int j=1; j<=num && !q.empty(); j++) q.pop();
        if(!q.empty() && i-q.front() >= d) {
            return 0;
        }
    }
    return 1;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> d >> m;
    for(int i=1; i<=m; i++) {
        cin >> in;
        t[in].push_back(i);
    }
    while(l < r) {
        mid = (l+r)>>1;
        if(solve(mid)) {
            r = mid;
        } else {
            l = mid+1;
        }
    }
    cout << l << "\n";
    queue<int> q;
    for(int i=1; i<=n; i++) {
        for(int j: t[i]) q.push(j);
        for(int j=1; j<=l && !q.empty(); j++) {
            cout << q.front() << " ";
            q.pop();
        }
        cout << "0\n";
    }
    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'bool solve(int)':
jobs.cpp:11:17: warning: unused variable 'j' [-Wunused-variable]
   11 |         for(int j: t[i]) q.push(i);
      |                 ^

• Subtask 1: 100 / 100