Submission #675716

#	Time	Username	Problem	Language	Result	Execution time	Memory
675716		aaggupta07	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	348 ms	22216 KiB

jobs

// Source: https://usaco.guide/general/io

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

#define MAX_C 1'000'001
#define pb push_back
#define pi pair<int, int>
#define f first
#define s second

int n, d, m;
vector<pi> requests;


bool check(int r) {
    int days = 0, jobsDone = 0;
    for(int i = 0; i < m; ++i) {
        // process r requests per day
        if(requests[i].f > days) {
            days = requests[i].f;
            ++jobsDone;
            continue;
        }
        if(jobsDone % r == 0) days += 1;
        if(days - requests[i].f > d) return false;

        ++jobsDone;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> d >> m;
    requests.resize(m);
    for(int i = 0; i < m; ++i) {
        cin >> requests[i].f;
        requests[i].s = i + 1;
    }

    sort(requests.begin(), requests.end());

    int ans = MAX_C;
    for(int b = MAX_C/2; b >= 1; b/=2) {
        while(ans - b >= 1 && check(ans - b)) ans -= b;
    }
    cout << ans << '\n';

    int days = 0, jobsDone = 0;
    vector<vector<int>> schedule(n);

    for(int i = 0; i < m; ++i) {
        // process r requests per day
        if(requests[i].f > days) days = requests[i].f;
        else if(jobsDone % ans == 0) days += 1;
        ++jobsDone;
        schedule[days-1].pb(requests[i].s);
    }

    for(auto& i: schedule) {
        for(int j: i) cout << j << ' '; cout << 0 << '\n';
    }
    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:62:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   62 |         for(int j: i) cout << j << ' '; cout << 0 << '\n';
      |         ^~~
jobs.cpp:62:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   62 |         for(int j: i) cout << j << ' '; cout << 0 << '\n';
      |                                         ^~~~

• Subtask 1: 90 / 100