oj.uz

답안 #995743

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

# 결과 실행 시간 메모리 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