Submission #557331

#	Time	Username	Problem	Language	Result	Execution time	Memory
557331		Ai7081	Job Scheduling (CEOI12_jobs)	C++17	50 / 100	199 ms	13932 KiB

jobs

#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 (p) printf("0\n");
    }
    return now == n+1;
}

int bs(int l, int r) {
    if (l == r) return l;
    int mid = (l+r)/2;
    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
*/

Compilation message (stderr)

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: In function 'int main()':
jobs.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf(" %d %d %d", &n, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:34:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     for (int i=1; i<=m; i++) scanf(" %d", &in), v[in].push_back(i);
      |                              ~~~~~^~~~~~~~~~~~

• Subtask 1: 50 / 100