Submission #768294

#	Time	Username	Problem	Language	Result	Execution time	Memory
768294		orcslop	Job Scheduling (CEOI12_jobs)	C++17	15 / 100	197 ms	13724 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size() 

const int MAXN = 1e5; 
const int MAXM = 1e6; 

int n, d, m; 
pair<int, int> jobs[MAXM]; 
queue<int> q; 

bool check(int machines){
    while(!q.empty()) q.pop(); 
    int index = 0; 
    for(int i = 1; i <= n; i++){
        while(index < m && jobs[index].first <= i) {
            q.push(jobs[index].first); 
            index++; 
        }
        for(int i = 0; i < machines; i++){
            if(!q.empty()) {
                int sent = q.front(); 
                if(i - sent > d) return false; 
                q.pop(); 
            }
            else break; 
        }
    }
    return q.empty(); 
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> d >> m; 
    for(int i = 0; i < m; i++) {
        cin >> jobs[i].first;
        jobs[i].second = i + 1;  
    }
    sort(jobs, jobs + m); 
    int low = 1, high = m; 
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (check(mid)) high = mid;
        else low = mid + 1;
    }
    cout << low << '\n'; 

    while(!q.empty()) q.pop(); 
    int index = 0; 
    for(int i = 1; i <= n; i++){
        while(index < m && jobs[index].first <= i) {
            q.push(jobs[index].second); 
            index++; 
        }
        for(int i = 0; i < low; i++){
            if(!q.empty()) {
                int sent = q.front(); 
                cout << sent << ' '; 
                q.pop(); 
            }
            else break; 
        }
        cout << "0\n"; 
    }
    return 0; 
}

• Subtask 1: 15 / 100