Submission #1281124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281124		cjspd_oly	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	98 ms	20088 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;

using pii = pair<int, int>;
using vii = vector<pii>;
using vvii = vector<vii>;

using l = long long;
using vl = vector<l>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;

using pll = pair<l, l>;
using vll = vector<pll>;
using vvll = vector<vll>;

// using d = double;
// using vd = vector<d>;
// using vvd = vector<vd>;
// using vvvd = vector<vvd>;

using ld = long double;
using vld = vector<ld>;
using vvld = vector<vld>;
using vvvld = vector<vvld>;

using vb = vector<bool>;
using vvb = vector<vb>;
using pbb = pair<bool, bool>;
using vbb = vector<pbb>;

#define ff first
#define ss second

#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

void setIO(string name = "")
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (!name.empty())
    {
        (void)freopen((name + ".in").c_str(), "r", stdin);
        (void)freopen((name + ".out").c_str(), "w", stdout);
    }
}

const ld pi = 3.14159265358979323846;

const l LINF = 1e18;
const l INF = 1e9;

const l MOD = 1e9 + 7;
// const l MOD = 998244353;

const l MAXN = 1e5 + 5;

int n, d, m;
vvi task(MAXN), // * task[day]: list of job IDs that arrive on day
    res(MAXN);  // * res[day]: list of job IDs scheduled to run on day

bool check(int x)
{
    deque<pii> q; // * {last_submit_day,cnt_of_job_in_batch}

    for (int i = 0; i < n; ++i)
    {
        if (task[i].size())
            q.pb({i + d, task[i].size()});

        int machines = x;
        while (machines > 0 && q.size())
        {
            auto [_, todo] = q.front();
            q.pop_front();

            if (machines >= todo)
                machines -= todo;
            else
            {
                todo -= machines;
                machines = 0;
                q.push_front({_, todo});
            }
        }

        if (q.size() && q.front().first <= i)
            return false;
    }
    return true;
}

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

    for (int i = 1; i <= m; ++i)
    {
        int x;
        cin >> x;
        task[x].pb(i);
    }

    int lo = 1, hi = m, ans = hi;
    while (lo <= hi)
    {
        int mid = (lo + hi) >> 1;
        if (check(mid))
        {
            ans = mid;
            hi = mid - 1;
        }
        else
            lo = mid + 1;
    }

    cout << ans << '\n';

    deque<int> q; // processing
    for (int i = 1; i <= n; ++i)
    {
        for (int &x : task[i])
            q.pb(x);
            
        int machine = ans;
        while (machine > 0 && q.size())
        {
            --machine;
            res[i].pb(q.front());
            q.pop_front();
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        sort(all(res[i]));
        for (int &x : res[i])
            cout << x << ' ';
        cout << "0\n";
    }
}

int main()
{
    setIO("");

#ifndef ONLINE_JUDGE
    // setIO("filename");
#endif

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4

2
5 1 0
9 4 0
2 10 0
6 12 0
3 7 0
11 8 0
0
0

https://oj.uz/problem/view/CEOI12_jobs

*/

Compilation message (stderr)

jobs.cpp: In function 'void setIO(std::string)':
jobs.cpp:52:22: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         (void)freopen((name + ".in").c_str(), "r", stdin);
      |               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:53:22: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         (void)freopen((name + ".out").c_str(), "w", stdout);
      |               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100