Submission #912596

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
912596	2024-01-19T16:17:00 Z	randomlurker	Job Scheduling (CEOI12_jobs)	C++17	45 / 100	1000 ms	65536 KB

jobs

#include <bits/stdc++.h>

typedef long long ll;
typedef long double ld;
using namespace std;

int n, d, m;
priority_queue<int, vector<int>, greater<>> reqs;
priority_queue<int, vector<int>, greater<>> reqsCopy;
priority_queue<int, vector<int>, greater<>> pq;
map<int, queue<int>> locs;

bool test(int x){
    for(int day=reqs.top(); day<n; day++){
        if (empty(pq) and empty(reqs)) break;
        while (!empty(reqs) and reqs.top() <= day) {
            pq.push(reqs.top() + d);
            reqs.pop();
        }
        for(int i=0; i<x; i++){
            // Complete the x tasks that are due soonest. If any are overdue, then return false
            if (day > pq.top()) return false;
            else pq.pop();
            if (empty(pq)) break;
        }
    }
    return (empty(pq));
}

int main() {
    cin >> n >> d >> m;
    int x;
    for(int i=1; i<=n; i++){
        locs.insert({i, {}});
    }
    for(int i=0; i<m; i++){
        cin >> x;
        reqs.push(x);
        locs[x].push(i+1);
    }
    int lo = 1;
    int hi = INT_MAX;
    int mid;
    reqsCopy = priority_queue<int, vector<int>, greater<>> (reqs);
    while(lo < hi){
        reqs = priority_queue<int, vector<int>, greater<>> (reqsCopy);
        pq = {};
        mid = lo + (hi-lo)/2;
        if (test(mid)){
            hi = mid;
        }
        else lo = mid+1;
    }
    cout << lo << endl;

    // Print out optimal movements
    reqs = priority_queue<int, vector<int>, greater<>> (reqsCopy);
    pq = {};
    string dayOut;
    for(int day=1; day<=n; day++){
        dayOut = "";
        while (!empty(reqs) and reqs.top() <= day) {
            pq.push(reqs.top() + d);
            reqs.pop();
        }
        for(int i=0; i<lo; i++){
            if (empty(pq)) break;
            else{
                int goodIdx = locs[pq.top()-d].front();
                locs[pq.top()-d].pop();
                dayOut += to_string(goodIdx) + " ";
                pq.pop();
            }
        }
        dayOut += "0";
        cout << dayOut << endl;
    }
    return 0;
}

/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
 */

Subtask #1

45.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	158 ms	10952 KB	Output is correct
2	Correct	164 ms	11080 KB	Output is correct
3	Correct	169 ms	11692 KB	Output is correct
4	Correct	164 ms	10976 KB	Output is correct
5	Correct	166 ms	10848 KB	Output is correct
6	Correct	157 ms	10848 KB	Output is correct
7	Correct	160 ms	11004 KB	Output is correct
8	Correct	158 ms	10836 KB	Output is correct
9	Runtime error	59 ms	65536 KB	Execution killed with signal 9
10	Runtime error	58 ms	65536 KB	Execution killed with signal 9
11	Correct	352 ms	3476 KB	Output is correct
12	Incorrect	804 ms	6272 KB	Output isn't correct
13	Execution timed out	1049 ms	8264 KB	Time limit exceeded
14	Execution timed out	1079 ms	14168 KB	Time limit exceeded
15	Execution timed out	1064 ms	10612 KB	Time limit exceeded
16	Execution timed out	1016 ms	18444 KB	Time limit exceeded
17	Execution timed out	1080 ms	19260 KB	Time limit exceeded
18	Execution timed out	1022 ms	23808 KB	Time limit exceeded
19	Runtime error	54 ms	65536 KB	Execution killed with signal 9
20	Execution timed out	1040 ms	19980 KB	Time limit exceeded