oj.uz

Submission #502650

# Submission time Handle Problem Language Result Execution time Memory
502650 2022-01-06T11:42:08 Z banterbry Job Scheduling (CEOI12_jobs) C++17
100 / 100
 308 ms 31208 KB 
#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long 
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr << " " << to_string(H);debug_out(T...);}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

int N, M, D;
pi req[1000010];
vector<int> ans[100010];

int good(int x) {
    for (int i = 1; i <= N; ++i) ans[i].clear();

    int j = 1;
    for (int i = 1; i <= N; ++i) {
        for (int k = 0; k < x; ++k) {
            if (req[j].fi > i) break;
            if (req[j].fi + D >= i) ans[i].pb(req[j++].si);
            else return 0;
            if (j == M + 1) return 1;
        }
    }
    return 0;
}   

int32_t main() {
    fast;
    cin >> N >> D >> M;
    for (int i = 1; i <= M; ++i) {
        cin >> req[i].fi;
        req[i].si = i;
    }
    sort(req + 1, req + 1 + M);
    int lo = 0, hi = 1e9;
    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if (good(mid)) hi = mid;
        else lo = mid;
    }
    cout << hi << '\n';
    good(hi);
    for (int i = 1; i <= N; ++i) {
        for (auto j: ans[i]) cout << j << ' ';
        cout << 0 << '\n';
    }
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6440 KB Output is correct
2 Correct 26 ms 6436 KB Output is correct
3 Correct 26 ms 6432 KB Output is correct
4 Correct 26 ms 6464 KB Output is correct
5 Correct 27 ms 6440 KB Output is correct
6 Correct 26 ms 6488 KB Output is correct
7 Correct 27 ms 6464 KB Output is correct
8 Correct 36 ms 6432 KB Output is correct
9 Correct 49 ms 6020 KB Output is correct
10 Correct 40 ms 5956 KB Output is correct
11 Correct 33 ms 5784 KB Output is correct
12 Correct 65 ms 9120 KB Output is correct
13 Correct 99 ms 13260 KB Output is correct
14 Correct 153 ms 16956 KB Output is correct
15 Correct 157 ms 19140 KB Output is correct
16 Correct 211 ms 23464 KB Output is correct
17 Correct 245 ms 29252 KB Output is correct
18 Correct 266 ms 28868 KB Output is correct
19 Correct 308 ms 31208 KB Output is correct
20 Correct 266 ms 29304 KB Output is correct