oj.uz

Submission #995755

# Submission time Handle Problem Language Result Execution time Memory
995755 2024-06-09T21:19:34 Z catsarecool5530 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 177 ms 14300 KB 
#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 valid(int machines) {
    int index = 0;
    int curmaxdelay = 0;
    for (int i = 0; i < n && index < m; i++) {
        //cerr << i << endl;
        int used = 0;
        curmaxdelay = max(curmaxdelay, i - whine[index].first);
        if (curmaxdelay > maxDelay) return false;
        while (used < machines && index < m && whine[index].first <= i) {
            //cerr << whine[index].second << " ";
            used++;
            index++;
        }
        //cerr << "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 ((valid(mid))) {
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    //cout << valid(2) << endl;

    cout << lo << endl;

    // this problem is a whiner who wants the answers to everything
    int machines = lo;
    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";
    }


}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1884 KB Output is correct
2 Correct 13 ms 1884 KB Output is correct
3 Correct 13 ms 1880 KB Output is correct
4 Correct 13 ms 1896 KB Output is correct
5 Correct 13 ms 1884 KB Output is correct
6 Correct 13 ms 1880 KB Output is correct
7 Correct 13 ms 1720 KB Output is correct
8 Correct 13 ms 1884 KB Output is correct
9 Correct 21 ms 2392 KB Output is correct
10 Correct 21 ms 2388 KB Output is correct
11 Correct 19 ms 1628 KB Output is correct
12 Correct 39 ms 3304 KB Output is correct
13 Correct 64 ms 4692 KB Output is correct
14 Correct 82 ms 6228 KB Output is correct
15 Correct 96 ms 7692 KB Output is correct
16 Correct 121 ms 9296 KB Output is correct
17 Correct 146 ms 10572 KB Output is correct
18 Correct 159 ms 12116 KB Output is correct
19 Correct 177 ms 14300 KB Output is correct
20 Correct 154 ms 10588 KB Output is correct