Submission #574545

#	Time	Username	Problem	Language	Result	Execution time	Memory
574545		havingfun854	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	277 ms	13940 KiB

jobs

// https://oj.uz/problem/view/CEOI12_jobs
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define forint(i, from, toinc) for (int i = from; i <= toinc; ++i)

void fio()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef USEFILE
    freopen("jobs.in", "r", stdin);
    freopen("jobs.out", "w", stdout);
#endif
}

struct Job {
    int id;         // 1e6
    int submitted;  // 1e5
};
int dcnt, delay_limit, jcnt; // day count, .., jobs count
vector<Job> jobs;

void debug()
{
    cerr << "jobs:";
    for (auto &j : jobs) { cerr << " " << j.id << "s" << j.submitted; }
    cerr << endl;
}
void read_data()
{
    cin >> dcnt >> delay_limit >> jcnt;
    forint(i, 1, jcnt) {
        int submitted;
        cin >> submitted;
        jobs.push_back({i, submitted});
    }
    sort(all(jobs), [](const Job &j1, const Job &j2){
        if (j1.submitted == j2.submitted) {
            return j1.id > j2.id;
        } else {
            return j1.submitted < j2.submitted;
        }
    });
    // debug();
}

bool can(int mm, bool print_schedule=false)  // can process using mm machines within delay_limit
{
    int amcnt = mm; // available machine count
    queue<Job> jq;
    int today = 1;
    int nextji = 0;
    while (today <= dcnt) {
        while (amcnt > 0 && !jq.empty()) {
            if (today - jq.front().submitted > delay_limit)
                return false;
            if (print_schedule) { cout << jq.front().id << ' '; }
            jq.pop();
            amcnt--;
        }
        while (jobs[nextji].submitted == today) {
            if (amcnt > 0) {
                amcnt--;
                if (print_schedule) { cout << jobs[nextji].id << ' '; }
            } else {
                jq.push(jobs[nextji]);
            }
            nextji++;
        }
        if (print_schedule) { cout << "0\n"; }
        today++;
        amcnt = mm;
    }

    return true;
}

int main()
{
    fio();
    read_data();

    int l = 0;      // ! can
    int r = jcnt;   // can, no delay
    while (l+1 < r) {
        int m = l + (r-l)/2;
        if (can(m)) {
            r = m;
        } else {
            l = m;
        }
    }
    cout << r << '\n';
    can(r, true);

    return 0;
}

• Subtask 1: 100 / 100