oj.uz

Submission #743202

# Submission time Handle Problem Language Result Execution time Memory
743202 2023-05-17T08:49:56 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+10];
int arr[N+10];
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 287 ms 34264 KB Memory limit exceeded
2 Runtime error 283 ms 34264 KB Memory limit exceeded
3 Runtime error 298 ms 34244 KB Memory limit exceeded
4 Runtime error 303 ms 34264 KB Memory limit exceeded
5 Runtime error 301 ms 34244 KB Memory limit exceeded
6 Runtime error 312 ms 34328 KB Memory limit exceeded
7 Runtime error 302 ms 34248 KB Memory limit exceeded
8 Runtime error 282 ms 34240 KB Memory limit exceeded
9 Runtime error 272 ms 35020 KB Memory limit exceeded
10 Runtime error 321 ms 35224 KB Memory limit exceeded
11 Runtime error 227 ms 41096 KB Memory limit exceeded
12 Runtime error 561 ms 65536 KB Execution killed with signal 9
13 Runtime error 853 ms 59008 KB Memory limit exceeded
14 Runtime error 687 ms 65536 KB Execution killed with signal 9
15 Runtime error 769 ms 45520 KB Memory limit exceeded
16 Runtime error 968 ms 51904 KB Memory limit exceeded
17 Runtime error 940 ms 65536 KB Execution killed with signal 9
18 Execution timed out 1071 ms 65536 KB Time limit exceeded
19 Execution timed out 1086 ms 49420 KB Time limit exceeded
20 Runtime error 941 ms 65536 KB Execution killed with signal 9