Submission #995743

#	Time	Username	Problem	Language	Result	Execution time	Memory
995743		catsarecool5530	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	101 ms	22912 KiB

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 (stderr)

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