Submission #995753

#	Time	Username	Problem	Language	Result	Execution time	Memory
995753		catsarecool5530	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	130 ms	9436 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl "\n"

struct Line {
    int start, end;
};

int maxDelay;
vector<int> schedule;
vector<pair<int, int>> whine;
int n, m;
bool works(int machines) {
    int index = 0;
    int curmaxdelay = 0;
    for (int i = 0; i < n; i++) {
        int used = 0;
        curmaxdelay = max(curmaxdelay, i - whine[index].first);
        while (used < machines && index < m && whine[index].first <= i) {
            //cout << whine[index].second << " ";
            used++;
            index++;
        }
        //cout << "0\n";
    }
    return curmaxdelay <= maxDelay;
}

// bool works(int machines) {
//     deque<pair<int, int>> todo;

//     int day = 0;
//     int currentmaxdelay = 0;
//     while (day < (int) schedule.size() || !todo.empty()) {
//         todo.push_back({day, schedule[day]});
//         currentmaxdelay = max(currentmaxdelay, day - todo.front().first);
//         if (currentmaxdelay > maxDelay) return false;
//         int machinesAvailible = machines;

//         while (!todo.empty() && machinesAvailible > 0) {
//             if (todo.front().second > machinesAvailible) {
//                 todo.front().second -= machinesAvailible;
//                 machinesAvailible = 0;
//             } else {
//                 machinesAvailible -= todo.front().second;
//                 todo.pop_front();
//             }
//         }
//         //cout << day << endl;


//         day++;
//     }   

//     return currentmaxdelay <= maxDelay; 
// }



int main() {
    // fast io
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
	//freopen("snowboots.in", "r", stdin);
    //freopen("snowboots.out", "w", stdout);      
    int d; cin >> n >> d >> m;
    maxDelay = d;
    schedule = vector<int>(n);
    whine = vector<pair<int, int>>(m); // day, ID

    for (int i = 0; i < m; i++) {
        int temp; cin >> temp;
        temp--;
        schedule[temp]++;
        whine[i] = {temp, i+1};
    }
    sort(whine.begin(), whine.end());

    int lo = 1; int hi = 1e9;

    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if ((works[mid])) {
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }

    cout << lo + 1 << endl;

    // this problem is a whiner who wants the answers to everything
    int machines = lo + 1;
    int index = 0;
    for (int i = 0; i < n; i++) {
        int used = 0;
        while (used < machines && index < m && whine[index].first <= i) {
            cout << whine[index].second << " ";
            used++;
            index++;
        }
        cout << "0\n";
    }


}

    
    

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:84:23: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   84 |         if ((works[mid])) {
      |                       ^

• Subtask 1: 0 / 100