Submission #574545

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
574545	2022-06-08T18:56:35 Z	havingfun854	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	277 ms	13940 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	2264 KB	Output is correct
2	Correct	25 ms	2268 KB	Output is correct
3	Correct	23 ms	2244 KB	Output is correct
4	Correct	22 ms	2248 KB	Output is correct
5	Correct	23 ms	2244 KB	Output is correct
6	Correct	23 ms	2272 KB	Output is correct
7	Correct	29 ms	2272 KB	Output is correct
8	Correct	23 ms	2260 KB	Output is correct
9	Correct	33 ms	2024 KB	Output is correct
10	Correct	36 ms	2032 KB	Output is correct
11	Correct	27 ms	1840 KB	Output is correct
12	Correct	60 ms	3392 KB	Output is correct
13	Correct	87 ms	4776 KB	Output is correct
14	Correct	123 ms	6612 KB	Output is correct
15	Correct	137 ms	7828 KB	Output is correct
16	Correct	179 ms	9488 KB	Output is correct
17	Correct	208 ms	10864 KB	Output is correct
18	Correct	247 ms	12364 KB	Output is correct
19	Correct	277 ms	13940 KB	Output is correct
20	Correct	210 ms	10884 KB	Output is correct