oj.uz

Submission #742992

# Submission time Handle Problem Language Result Execution time Memory
742992 2023-05-17T07:17:02 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
0 / 100
 1000 ms 65536 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];
int arr[N];
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 + 100;
    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 242 ms 34644 KB Memory limit exceeded
2 Runtime error 249 ms 34528 KB Memory limit exceeded
3 Runtime error 259 ms 34632 KB Memory limit exceeded
4 Runtime error 261 ms 34548 KB Memory limit exceeded
5 Runtime error 265 ms 34584 KB Memory limit exceeded
6 Runtime error 256 ms 34524 KB Memory limit exceeded
7 Runtime error 277 ms 34632 KB Memory limit exceeded
8 Runtime error 246 ms 34572 KB Memory limit exceeded
9 Runtime error 228 ms 34992 KB Memory limit exceeded
10 Runtime error 287 ms 35656 KB Memory limit exceeded
11 Runtime error 188 ms 40700 KB Memory limit exceeded
12 Execution timed out 1086 ms 32648 KB Time limit exceeded
13 Runtime error 61 ms 65536 KB Execution killed with signal 11
14 Runtime error 89 ms 65536 KB Execution killed with signal 11
15 Execution timed out 1081 ms 33484 KB Time limit exceeded
16 Runtime error 82 ms 65536 KB Execution killed with signal 11
17 Execution timed out 1042 ms 33668 KB Time limit exceeded
18 Runtime error 86 ms 65536 KB Execution killed with signal 11
19 Runtime error 97 ms 65536 KB Execution killed with signal 11
20 Execution timed out 1026 ms 33684 KB Time limit exceeded