oj.uz

Submission #232211

# Submission time Handle Problem Language Result Execution time Memory
232211 2020-05-16T11:40:22 Z DodgeBallMan Job Scheduling (CEOI12_jobs) C++14
100 / 100
 357 ms 23672 KB 
#include <bits/stdc++.h>
 
#define pii pair<int, int>
#define x first
#define y second
 
using namespace std;
 
const int N = 1e5+5;
 
int n, m, d;
vector<int> job[N], ans[N];
 
bool solve(int mid) {
    queue<pii> Q;
    for(int i = 1; i <= n; i++) ans[i].clear();
    for(int i = 1; i <= n; i++) {
        for(int x : job[i]) Q.emplace(x, i);
        while(!Q.empty() && ans[i].size() < mid) {
            pii now = Q.front(); Q.pop();
            if(now.y + d < i) return false;
            ans[i].emplace_back(now.x);
        } 
    }
    return Q.empty();
}
 
int main() {
    scanf("%d %d %d", &n, &d, &m);
    for(int i = 1, a; i <= m; i++) {
        scanf("%d", &a);
        job[a].emplace_back(i);
    }
    int l = 0, r = (int)1e6;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(solve(mid)) r = mid;
        else l = mid + 1;
    }
    solve(r);
    printf("%d\n", r);
    for(int i = 1; i <= n; i++) {
        for(int x : ans[i]) printf("%d ", x);
        printf("0\n");
    }
 
    return 0;
}

Compilation message

jobs.cpp: In function 'bool solve(int)':
jobs.cpp:19:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(!Q.empty() && ans[i].size() < mid) {
                             ~~~~~~~~~~~~~~^~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &d, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a);
         ~~~~~^~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 7288 KB Output is correct
2 Correct 48 ms 7288 KB Output is correct
3 Correct 49 ms 7288 KB Output is correct
4 Correct 49 ms 7288 KB Output is correct
5 Correct 50 ms 7304 KB Output is correct
6 Correct 50 ms 7288 KB Output is correct
7 Correct 48 ms 7312 KB Output is correct
8 Correct 49 ms 7368 KB Output is correct
9 Correct 56 ms 7288 KB Output is correct
10 Correct 54 ms 7288 KB Output is correct
11 Correct 46 ms 7032 KB Output is correct
12 Correct 91 ms 9332 KB Output is correct
13 Correct 124 ms 12408 KB Output is correct
14 Correct 192 ms 15648 KB Output is correct
15 Correct 200 ms 15992 KB Output is correct
16 Correct 281 ms 19448 KB Output is correct
17 Correct 329 ms 23672 KB Output is correct
18 Correct 317 ms 22008 KB Output is correct
19 Correct 357 ms 23288 KB Output is correct
20 Correct 335 ms 23672 KB Output is correct