Submission #267142

#	Time	Username	Problem	Language	Result	Execution time	Memory
267142		Sorting	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	281 ms	13688 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

const int k_N = 1e5 + 3;
const int k_M = 1e6 + 3;

int n, d, m;
vector<int> jobs[k_N];

bool check(int mid){
    queue<int> q;
    for(int i = 1; i <= n; ++i){
        for(int x: jobs[i])
            q.push(i);

        int t = mid;
        while(t-- && !q.empty()){
            if(q.front() + d < i)
                return false;
            q.pop();
        }
    }
    return true;
}

void output(int mid){
    queue<int> q;
    for(int i = 1; i <= n; ++i){
        for(int x: jobs[i])
            q.push(x);

        int t = mid;
        while(t-- && !q.empty()){
            cout << q.front() << " ";
            q.pop();
        }
        cout << "0\n";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

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

    int l = 0, r = k_M;
    while(l != r){
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << l << "\n";
    output(l);    
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

Compilation message (stderr)

jobs.cpp: In function 'bool check(int)':
jobs.cpp:14:17: warning: unused variable 'x' [-Wunused-variable]
   14 |         for(int x: jobs[i])
      |                 ^

• Subtask 1: 100 / 100