Submission #557320

#	Time	Username	Problem	Language	Result	Execution time	Memory
557320		Ai7081	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	157 ms	13884 KiB

jobs

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

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

int bs(int l, int r) {
    if (l == r) return l;
    int mid = (l+r)/2;
    bool fail = false;
    for (int i=1; i<=n-d; i++) {
        if (sum[i] > (d+i)*mid) {fail = true; break;}
    }
    if (fail) return bs(mid+1, r);
    else return bs(l, mid);
}

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();
    int x = bs(1, 10000000);
    printf("%d\n", x);
    int now=1, point=0;
    for (int i=1; i<=n; i++) {
        int cnt = x;
        while (now <= i && cnt--) {
            if (point >= v[now].size()) {now++, point=0, cnt++; continue;}
            printf("%d ", v[now][point++]);
        }
        printf("0\n");
    }
    return 0;
}

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

Compilation message (stderr)

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

• Subtask 1: 0 / 100