Submission #995747

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
995747	2024-06-09T21:01:16 Z	catsarecool5530	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	1000 ms	65536 KB

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;

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; 
}

struct Ordering {
    vector<int> arr;
    int index = 0;
};


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 n, d, m; cin >> n >> d >> m;
    maxDelay = d;
    schedule = vector<int>(n);
    vector<Ordering> orders(n);

    for (int i = 0; i < m; i++) {
        int temp; cin >> temp;
        temp--;
        schedule[temp]++;
        orders[temp].arr.push_back(i+1);
    }

    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;

    deque<pair<int, int>> todo;

    int day = 0;
    while (day < (int) schedule.size() || !todo.empty()) {
        todo.push_back({day, schedule[day]});

        int machinesAvailible = machines;

        while (!todo.empty() && machinesAvailible > 0) {
            if (todo.front().second > machinesAvailible) {
                todo.front().second -= machinesAvailible;

                // for (int i = orders[todo.front().first].index; 
                // i < orders[todo.front().first].index + machinesAvailible; i++) {
                //     cout << orders[todo.front().first].arr.at(i) << " ";
                // }
                orders[todo.front().first].index += machinesAvailible;
                machinesAvailible = 0;
            } else {
                machinesAvailible -= todo.front().second;
                for (int i = orders[todo.front().first].index;
                 i < (int) orders[todo.front().first].arr.size(); i++) {
                     cout << orders[todo.front().first].arr.at(i) << " ";
                 }
                todo.pop_front();
            }
        }
        //cout << day << endl;

        cout << "0\n";
        day++;
    }   


}

    
    

Compilation message

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

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	224 ms	65536 KB	Execution killed with signal 9
2	Runtime error	236 ms	65536 KB	Execution killed with signal 9
3	Runtime error	176 ms	65536 KB	Execution killed with signal 9
4	Runtime error	229 ms	65536 KB	Execution killed with signal 9
5	Runtime error	251 ms	65536 KB	Execution killed with signal 9
6	Runtime error	253 ms	65536 KB	Execution killed with signal 9
7	Runtime error	232 ms	65536 KB	Execution killed with signal 9
8	Runtime error	198 ms	65536 KB	Execution killed with signal 9
9	Incorrect	9 ms	4956 KB	Output isn't correct
10	Incorrect	8 ms	4956 KB	Output isn't correct
11	Runtime error	8 ms	2908 KB	Execution killed with signal 11
12	Runtime error	18 ms	4700 KB	Execution killed with signal 11
13	Runtime error	234 ms	65536 KB	Execution killed with signal 9
14	Runtime error	205 ms	65536 KB	Execution killed with signal 9
15	Execution timed out	2288 ms	65536 KB	Time limit exceeded
16	Runtime error	260 ms	65536 KB	Execution killed with signal 9
17	Runtime error	273 ms	65536 KB	Execution killed with signal 9
18	Runtime error	54 ms	17580 KB	Execution killed with signal 11
19	Runtime error	50 ms	17744 KB	Execution killed with signal 11
20	Runtime error	265 ms	65536 KB	Execution killed with signal 9