oj.uz

Submission #557333

# Submission time Handle Problem Language Result Execution time Memory
557333 2022-05-05T07:03:47 Z Ai7081 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 179 ms 13928 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int n, m, d, in, sum[N];
vector<int> v[N];

bool run(int x, bool p) {
    int now=1, point=0;
    if (p) printf("%d\n", x);
    for (int i=1; i<=n; i++) {
        int cnt = x;
        if (now+d < i) return false;
        while (now <= i && cnt--) {
            if (point >= v[now].size()) {now++, point=0, cnt++; continue;}
            if (p) printf("%d ", v[now][point]);
            point++;
        }
        if (point >= v[now].size()) now++, point=0;
        if (p) printf("0\n");
    }
    return true;
}

int bs(int l, int r) {
    if (l == r) return l;
    int mid = (l+r)/2;
//    printf("bs %d %d\n", l, r);
    if (run(mid, 0)) return bs(l, mid);
    return bs(mid+1, r);
}

int main() {
    scanf(" %d %d %d", &n, &d, &m);
    for (int i=1; i<=m; i++) scanf(" %d", &in), v[in].push_back(i);
    for (int i=1; i<=n; i++) sum[i] = sum[i-1] + v[i].size();
    run(bs(1, 1000000), 1);
    return 0;
}

/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4

5 0 6
1 3 4 3 2 5
*/

Compilation message

jobs.cpp: In function 'bool run(int, bool)':
jobs.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |             if (point >= v[now].size()) {now++, point=0, cnt++; continue;}
      |                 ~~~~~~^~~~~~~~~~~~~~~~
jobs.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         if (point >= v[now].size()) now++, point=0;
      |             ~~~~~~^~~~~~~~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf(" %d %d %d", &n, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:36:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     for (int i=1; i<=m; i++) scanf(" %d", &in), v[in].push_back(i);
      |                              ~~~~~^~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3780 KB Output is correct
2 Correct 20 ms 3756 KB Output is correct
3 Correct 23 ms 3736 KB Output is correct
4 Correct 23 ms 3744 KB Output is correct
5 Correct 32 ms 3780 KB Output is correct
6 Correct 21 ms 3700 KB Output is correct
7 Correct 24 ms 3736 KB Output is correct
8 Correct 20 ms 3788 KB Output is correct
9 Correct 28 ms 4392 KB Output is correct
10 Correct 26 ms 4444 KB Output is correct
11 Correct 22 ms 3800 KB Output is correct
12 Correct 40 ms 4876 KB Output is correct
13 Correct 62 ms 6876 KB Output is correct
14 Correct 109 ms 8048 KB Output is correct
15 Correct 104 ms 9036 KB Output is correct
16 Correct 145 ms 10792 KB Output is correct
17 Correct 163 ms 12644 KB Output is correct
18 Correct 163 ms 12652 KB Output is correct
19 Correct 179 ms 13928 KB Output is correct
20 Correct 172 ms 12596 KB Output is correct