Submission #1258803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258803		tkhoi13	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	80 ms	13640 KiB

jobs

#include <bits/stdc++.h>
#define ll long long
#define db double
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define all(x) begin(x), end(x)
#define allr(x) rbegin(x), rend(x)
#define szx(x) ((int)(x).size())
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; ++i)
#define ROF(i, a, b) for (int i = a, _b = (b); i >= _b; --i)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define endl '\n'
#define inf 1000000007
#define mod 1000000007

using namespace std;

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

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

    vector<vector<int>> tasks(n);

    REP(i, m) {
        int t;
        cin >> t;
        tasks[t - 1].pb(i);
    }

    auto f = [&](int x) -> bool {
        deque<pii> dq;
        REP(i, n) {
            int de = x;
            if (szx(tasks[i])) dq.pb({szx(tasks[i]), i});
            if (!dq.empty() && dq.front().se < i - d) return 0;
            while (!dq.empty() && de) {
                pii t = dq.front();
                dq.pop_front();
                int decrease = min(t.fi, de);
                de -= decrease;
                t.fi -= decrease;
                if (t.fi) dq.push_front(t);
            }
        }

        return dq.empty();
    };

    // REP(i, 10) cout << i << ' ' << f(i) << '\n';

    int l = 0, r = 1e9;
    while (l + 1 < r) {
        int x = (l + r) >> 1;
        // cout << l << ' ' << r << ' ' << x << ' ' << f(x) << '\n';
        if (f(x))
            r = x;
        else
            l = x;
    }

    cout << r << endl;
    queue<int> q;
    REP(i, n) {
        for (int t : tasks[i]) q.push(t);
        int de = r;
        while (!q.empty() && de) {
            cout << q.front() + 1 << ' ';
            q.pop();
            de--;
        }

        cout << 0 << '\n';
    }
}

int main() {
    setIO("cruise");
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100