oj.uz

Submission #995732

# Submission time Handle Problem Language Result Execution time Memory
995732 2024-06-09T20:29:06 Z catsarecool5530 Job Scheduling (CEOI12_jobs) C++17
0 / 100
 38 ms 4044 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 < 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; 
}


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);

    for (int i = 0; i < m; i++) {
        int temp; cin >> temp;
        temp--;
        schedule[temp]++;
    }

    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;



}

Compilation message

jobs.cpp: In function 'bool works(int)':
jobs.cpp:18:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     while (day < schedule.size() || !todo.empty()) {
      |            ~~~~^~~~~~~~~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:63:23: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   63 |         if (!works[mid]) {
      |                       ^

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 604 KB Output isn't correct
2 Incorrect 4 ms 604 KB Output isn't correct
3 Incorrect 6 ms 604 KB Output isn't correct
4 Incorrect 4 ms 604 KB Output isn't correct
5 Incorrect 4 ms 604 KB Output isn't correct
6 Incorrect 4 ms 604 KB Output isn't correct
7 Incorrect 4 ms 604 KB Output isn't correct
8 Incorrect 4 ms 604 KB Output isn't correct
9 Incorrect 4 ms 972 KB Output isn't correct
10 Incorrect 4 ms 860 KB Output isn't correct
11 Incorrect 5 ms 604 KB Output isn't correct
12 Incorrect 9 ms 1208 KB Output isn't correct
13 Incorrect 15 ms 1492 KB Output isn't correct
14 Incorrect 20 ms 2396 KB Output isn't correct
15 Incorrect 21 ms 2236 KB Output isn't correct
16 Incorrect 28 ms 3164 KB Output isn't correct
17 Incorrect 38 ms 3660 KB Output isn't correct
18 Incorrect 34 ms 3416 KB Output isn't correct
19 Incorrect 38 ms 4044 KB Output isn't correct
20 Incorrect 33 ms 3664 KB Output isn't correct