Submission #330608

#	Time	Username	Problem	Language	Result	Execution time	Memory
330608		ewang	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	791 ms	25684 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

#define MAXM 1000000
#define MAXN 100000
#define pb push_back
#define mp make_pair
#define f first
#define s second

int N, D, M;
pair<int, int> r[MAXM];
vector<int> ans[MAXN];

bool ok(int mid, bool last) {
    int prev[mid]; memset(prev, 0, sizeof prev);
    int day = -1;
    for (int i = 0; i < M; i++) {
        prev[i%mid]++;
        if (prev[i%mid]-r[i].f > D) {
            return 0;
        }

        if (last) {
            if (i%mid == 0) {
                day++;
            }
            ans[day].pb(r[i].s);
        }
    }
    return 1;
}

int main() {
    cin >> N >> D >> M;

    for (int i = 0; i < M; i++) {
        cin >> r[i].f;
        r[i].s = i+1;
    }
    sort(r, r+M);

    int a = 1, b = M;
    while (a != b) {
        int mid = (a+b)/2;
        if (ok(mid, false)) {
            b = mid;
        } else {
            a = mid+1;
        }
    }
    ok(a, true);
    
    cout << a << endl;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < ans[i].size(); j++) {
            cout << ans[i][j] << " ";
        }
        cout << 0 << endl;
    }
    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int j = 0; j < ans[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~

• Subtask 1: 55 / 100