Submission #1257322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257322		satyanshu	Job Scheduling (CEOI12_jobs)	C++20	0 / 100	22 ms	9988 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 7;
bool bipartite;
const int MAXN = 200005;
ll fact[MAXN];
ll h, c, t;
const ll NEG_INF = -1e17 - 7;

void solve()
{
    int n, m, d;
    cin >> n >> m >> d;

    vector<int> jobs(m);
    map<int, int> mp;
    vector<vector<int>> arrivals(n + 1);

    for (int i = 0; i < m; i++) {
        cin >> jobs[i];
        arrivals[jobs[i]].push_back(i + 1); // store job id by arrival day
        mp[jobs[i]]++;
        mp[jobs[i] + d + 1]--;
    }

    int ans = 0, active = 0;
    for (int i = 1; i <= n; i++) {
        active += mp[i];
        ans = max(ans, active);
    }

    cout << ans << endl;

    // Schedule banane ka part
    vector<vector<int>> schedule(n + 1);
    queue<pair<int, int>> q; // {job id, deadline}

    for (int day = 1; day <= n; day++) {
        // new arrivals
        for (int id : arrivals[day]) {
            q.push({id, day + d});
        }

        // remove expired
        while (!q.empty() && q.front().second < day) {
            q.pop();
        }

        // assign jobs today
        int jobsToday = 0;
        while (!q.empty() && jobsToday < ans) {
            schedule[day].push_back(q.front().first);
            q.pop();
            jobsToday++;
        }
    }

    // print schedule
    for (int day = 1; day <= n; day++) {
        for (int id : schedule[day]) cout << id << " ";
        cout << 0 << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

• Subtask 1: 0 / 100