Submission #592353

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
592353	2022-07-09T04:42:53 Z	Noble_Mushtak	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	173 ms	28280 KB

jobs

//replace Ofast with O3 for floating-point accuracy
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#include <bits/stdc++.h>

using num = int64_t;
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define REPI(t, n) for (num t = 0; t < n; ++t)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
#ifdef TESTING
#define DEBUG(...) __VA_ARGS__
#else
#define DEBUG(...)
#endif

bool possible(vector<vector<num>> &jobs, num D, num M) {
    num N = sz(jobs);
    vector<num> jobsLeft(N);
    num idx = 0;
    REPI(i, N) {
        if (idx+D < i) return false;
        
        jobsLeft[i] = sz(jobs[i]);
        num spent = 0;
        while (spent < M) {
            if (idx > i) break;
            num canSpend = min(M-spent, jobsLeft[idx]);
            jobsLeft[idx] -= canSpend;
            spent += canSpend;
            if (jobsLeft[idx] == 0) ++idx;
        }
    }
    while ((idx < N) && (jobsLeft[idx] == 0)) ++idx;
    return (idx == N);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

    num N, D, M;
    cin >> N >> D >> M;
    vector<vector<num>> jobs(N);
    REPI(i, M) {
        num x;
        cin >> x;
        --x;
        jobs[x].push_back(i+1);
    }
    num lo = 1, hi = M;
    while (lo < hi) {
        num mid = (lo+hi) >> 1;
        if (possible(jobs, D, mid)) hi = mid;
        else lo = mid+1;
    }

    queue<num> jobsPending;
    vector<vector<num>> ans(N);
    REPI(i, N) {
        for (num job : jobs[i]) jobsPending.push(job);
        REPI(j, lo) {
            if (jobsPending.empty()) break;
            num curJob = jobsPending.front();
            jobsPending.pop();
            ans[i].push_back(curJob);
        }
    }
    cout << lo << "\n";
    REPI(i, N) {
        for (num job : ans[i]) cout << job << " ";
        cout << "0\n";
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	4304 KB	Output is correct
2	Correct	15 ms	4304 KB	Output is correct
3	Correct	15 ms	4252 KB	Output is correct
4	Correct	20 ms	4228 KB	Output is correct
5	Correct	15 ms	4224 KB	Output is correct
6	Correct	15 ms	4212 KB	Output is correct
7	Correct	19 ms	4336 KB	Output is correct
8	Correct	20 ms	4304 KB	Output is correct
9	Correct	23 ms	8160 KB	Output is correct
10	Correct	25 ms	8144 KB	Output is correct
11	Correct	16 ms	3028 KB	Output is correct
12	Correct	31 ms	5668 KB	Output is correct
13	Correct	47 ms	10712 KB	Output is correct
14	Correct	78 ms	13728 KB	Output is correct
15	Correct	76 ms	13240 KB	Output is correct
16	Correct	112 ms	17012 KB	Output is correct
17	Correct	140 ms	25544 KB	Output is correct
18	Correct	124 ms	23244 KB	Output is correct
19	Correct	173 ms	28280 KB	Output is correct
20	Correct	135 ms	25464 KB	Output is correct