oj.uz

Submission #743277

# Submission time Handle Problem Language Result Execution time Memory
743277 2023-05-17T09:22:13 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
0 / 100
 1000 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
const int M = 1e6 + 1;
priority_queue<pair<int,int>> q[M+1000];
int arr[N+1000];
int n,d,m;
bool solve(int mid) {
    if (mid>=M) return true;
	for(int i=1;i<=m;i++) {
		while (!q[i].empty()) q[i].pop();
	}
    for(int i=1;i<=n;i++) {
        q[arr[i]].push({arr[i]+d, i});
    }
    for(int i=1;i<m;i++) {
        while (q[i].size()>mid) {
            auto [a,b] = q[i].top(); q[i].pop();
            if (a<=i) return false;
            q[i+1].push({a, b});
        }
    }
    return q[m].size() <= mid;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> m >> d >> n;
    for(int i=1;i<=n;i++) cin >> arr[i];
    int l = 1 , r = N;
    while (l < r) {
        int mid = (l + r) / 2;
        if (solve(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << '\n';
    solve(l);
    for(int i=1;i<=m;i++) {
    	while (!q[i].empty()) {
    		auto [a,b] = q[i].top(); q[i].pop();
    		cout << b << ' ';
		}
		cout << "0\n";
	}
    return 0;
}

Compilation message

jobs.cpp: In function 'bool solve(int)':
jobs.cpp:17:27: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   17 |         while (q[i].size()>mid) {
      |                ~~~~~~~~~~~^~~~
jobs.cpp:23:24: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |     return q[m].size() <= mid;
      |            ~~~~~~~~~~~~^~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 332 ms 34300 KB Memory limit exceeded
2 Runtime error 313 ms 34324 KB Memory limit exceeded
3 Runtime error 304 ms 34296 KB Memory limit exceeded
4 Runtime error 293 ms 34304 KB Memory limit exceeded
5 Runtime error 332 ms 34384 KB Memory limit exceeded
6 Runtime error 277 ms 34308 KB Memory limit exceeded
7 Runtime error 288 ms 34372 KB Memory limit exceeded
8 Runtime error 292 ms 34272 KB Memory limit exceeded
9 Runtime error 261 ms 35084 KB Memory limit exceeded
10 Runtime error 316 ms 35224 KB Memory limit exceeded
11 Runtime error 205 ms 41088 KB Memory limit exceeded
12 Runtime error 552 ms 65536 KB Execution killed with signal 9
13 Runtime error 835 ms 59060 KB Memory limit exceeded
14 Runtime error 634 ms 65536 KB Execution killed with signal 9
15 Runtime error 836 ms 45664 KB Memory limit exceeded
16 Runtime error 954 ms 52044 KB Memory limit exceeded
17 Runtime error 948 ms 65536 KB Execution killed with signal 9
18 Execution timed out 1069 ms 65536 KB Time limit exceeded
19 Execution timed out 1074 ms 47052 KB Time limit exceeded
20 Runtime error 864 ms 65536 KB Execution killed with signal 9