Submission #592353

#	Time	Username	Problem	Language	Result	Execution time	Memory
592353		Noble_Mushtak	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	173 ms	28280 KiB

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 / 100