Submission #706103

#	Time	Username	Problem	Language	Result	Execution time	Memory
706103		Bodisha	Job Scheduling (CEOI12_jobs)	C++17	45 / 100	354 ms	13780 KiB

jobs

#include <bits/stdc++.h>
#define MAX_M 1000000

using namespace std;

int n, d, m;
pair<int, int> requests[MAX_M];

bool cmp(pair<int, int> a, pair<int, int> b) {
    if(a.first == b.first) {
        return a.second < b.second;
    }
    return a.first < b.first;
}

bool check(int x) {
    int day = 1;
    int index = x - 1;
    while(index < m) {
        if(requests[index].first + d < day) {
            return false;
        }
        day++;
        if(index + x >= m) {
            index = m - 1;
            if(requests[index].first + d < day) {
                return false;
            } else {
                return true;
            }
        } else {
            index += x;
        }
    }
    return true;
}

int main() {
    cin >> n >> d >> m;
    for(int i = 0; i < m; i++) {
        cin >> requests[i].first;
        requests[i].second = i + 1;
    }
    sort(requests, requests + m, cmp);
    int l = 0, r = m;
    int ans = 1;
    while(l <= r) {
        int mid = l + (r - l) / 2;
        if(check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    } 
    cout << ans << "\n";
    int ptr = 0;
    for(int i = 0; i < n; i++) {
        int counter = 0;
        while(ptr < m && counter < ans) {
            cout << requests[ptr].second << " ";
            ptr++;
            counter++;
        }
        cout << "0\n";
    }
    return 0;
}

• Subtask 1: 45 / 100