Submission #995743

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
995743	2024-06-09T20:51:43 Z	catsarecool5530	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	101 ms	22912 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]) {
            lo = mid + 1;
        } else {
            hi = 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[i] << " ";
                }
                orders[todo.front().first].index += machinesAvailible;
                machinesAvailible = 0;
            } else {
                machinesAvailible -= todo.front().second;
                for (int i = orders[todo.front().first].index;
                 i < orders[todo.front().first].arr.size(); i++) {
                     cout << orders[todo.front().first].arr[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]) {
      |                       ^
jobs.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |                  i < orders[todo.front().first].arr.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	12 ms	3540 KB	Execution killed with signal 11
2	Runtime error	12 ms	3524 KB	Execution killed with signal 11
3	Runtime error	11 ms	3536 KB	Execution killed with signal 11
4	Runtime error	12 ms	3540 KB	Execution killed with signal 11
5	Runtime error	11 ms	3572 KB	Execution killed with signal 11
6	Runtime error	11 ms	3500 KB	Execution killed with signal 11
7	Runtime error	11 ms	3484 KB	Execution killed with signal 11
8	Runtime error	11 ms	3492 KB	Execution killed with signal 11
9	Incorrect	16 ms	5724 KB	Output isn't correct
10	Incorrect	13 ms	5652 KB	Output isn't correct
11	Runtime error	13 ms	3368 KB	Execution killed with signal 11
12	Runtime error	25 ms	5720 KB	Execution killed with signal 11
13	Runtime error	36 ms	9608 KB	Execution killed with signal 11
14	Runtime error	57 ms	12884 KB	Execution killed with signal 11
15	Runtime error	61 ms	14192 KB	Execution killed with signal 11
16	Runtime error	83 ms	18724 KB	Execution killed with signal 11
17	Runtime error	100 ms	22864 KB	Execution killed with signal 11
18	Runtime error	91 ms	22608 KB	Execution killed with signal 11
19	Runtime error	61 ms	19208 KB	Execution killed with signal 11
20	Runtime error	101 ms	22912 KB	Execution killed with signal 11