oj.uz

Submission #743137

# Submission time Handle Problem Language Result Execution time Memory
743137 2023-05-17T08:18:51 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
0 / 100
 1000 ms 64692 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
const int M = 1e6 + 1;
priority_queue<pair<int,int>> q[M+10];
int arr[N+10];
int n,d,m;
bool solve(int mid) {
	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:16: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]
   16 |         while (q[i].size()>mid) {
      |                ~~~~~~~~~~~^~~~
jobs.cpp:22: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]
   22 |     return q[m].size() <= mid;
      |            ~~~~~~~~~~~~^~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 297 ms 34236 KB Memory limit exceeded
2 Runtime error 296 ms 34244 KB Memory limit exceeded
3 Runtime error 331 ms 34292 KB Memory limit exceeded
4 Runtime error 321 ms 34336 KB Memory limit exceeded
5 Runtime error 293 ms 34236 KB Memory limit exceeded
6 Runtime error 282 ms 34236 KB Memory limit exceeded
7 Runtime error 278 ms 34248 KB Memory limit exceeded
8 Runtime error 264 ms 34220 KB Memory limit exceeded
9 Runtime error 242 ms 34756 KB Memory limit exceeded
10 Runtime error 328 ms 35376 KB Memory limit exceeded
11 Runtime error 191 ms 40312 KB Memory limit exceeded
12 Execution timed out 1079 ms 31956 KB Time limit exceeded
13 Runtime error 62 ms 64692 KB Execution killed with signal 11
14 Execution timed out 1071 ms 31956 KB Time limit exceeded
15 Runtime error 76 ms 64632 KB Execution killed with signal 11
16 Execution timed out 1090 ms 31956 KB Time limit exceeded
17 Execution timed out 1066 ms 32004 KB Time limit exceeded
18 Execution timed out 1083 ms 31956 KB Time limit exceeded
19 Runtime error 93 ms 64652 KB Execution killed with signal 11
20 Execution timed out 1074 ms 31956 KB Time limit exceeded