답안 #995745

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
995745	2024-06-09T20:57:49 Z	catsarecool5530	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	101 ms	22868 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[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[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

#	결과	실행 시간	메모리	Grader output
1	Runtime error	16 ms	3536 KB	Execution killed with signal 11
2	Runtime error	12 ms	3536 KB	Execution killed with signal 11
3	Runtime error	12 ms	3540 KB	Execution killed with signal 11
4	Runtime error	14 ms	3648 KB	Execution killed with signal 11
5	Runtime error	14 ms	3536 KB	Execution killed with signal 11
6	Runtime error	12 ms	3460 KB	Execution killed with signal 11
7	Runtime error	11 ms	3672 KB	Execution killed with signal 11
8	Runtime error	11 ms	3540 KB	Execution killed with signal 11
9	Incorrect	13 ms	5784 KB	Output isn't correct
10	Incorrect	12 ms	5724 KB	Output isn't correct
11	Runtime error	13 ms	3164 KB	Execution killed with signal 11
12	Runtime error	24 ms	5780 KB	Execution killed with signal 11
13	Runtime error	36 ms	9556 KB	Execution killed with signal 11
14	Runtime error	60 ms	12888 KB	Execution killed with signal 11
15	Runtime error	64 ms	14180 KB	Execution killed with signal 11
16	Runtime error	90 ms	18768 KB	Execution killed with signal 11
17	Runtime error	99 ms	22868 KB	Execution killed with signal 11
18	Runtime error	94 ms	22608 KB	Execution killed with signal 11
19	Runtime error	64 ms	19280 KB	Execution killed with signal 11
20	Runtime error	101 ms	22864 KB	Execution killed with signal 11