Submission #995746

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
995746	2024-06-09T20:59:53 Z	catsarecool5530	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	109 ms	22976 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	16 ms	3540 KB	Execution killed with signal 6
2	Runtime error	14 ms	3532 KB	Execution killed with signal 6
3	Runtime error	13 ms	3540 KB	Execution killed with signal 6
4	Runtime error	13 ms	3540 KB	Execution killed with signal 6
5	Runtime error	14 ms	3540 KB	Execution killed with signal 6
6	Runtime error	13 ms	3592 KB	Execution killed with signal 6
7	Runtime error	13 ms	3592 KB	Execution killed with signal 6
8	Runtime error	13 ms	3732 KB	Execution killed with signal 6
9	Incorrect	15 ms	5724 KB	Output isn't correct
10	Incorrect	13 ms	5720 KB	Output isn't correct
11	Runtime error	13 ms	3164 KB	Execution killed with signal 11
12	Runtime error	25 ms	5596 KB	Execution killed with signal 11
13	Runtime error	39 ms	9552 KB	Execution killed with signal 11
14	Runtime error	61 ms	12912 KB	Execution killed with signal 6
15	Runtime error	64 ms	14160 KB	Execution killed with signal 11
16	Runtime error	94 ms	19024 KB	Execution killed with signal 6
17	Runtime error	109 ms	22976 KB	Execution killed with signal 6
18	Runtime error	98 ms	22612 KB	Execution killed with signal 6
19	Runtime error	63 ms	19224 KB	Execution killed with signal 11
20	Runtime error	104 ms	22864 KB	Execution killed with signal 6