Submission #977270

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
977270	2024-05-07T15:27:55 Z	LOLOLO	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	143 ms	20304 KB

jobs

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
#define           f    first
#define           s    second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 1e5 + 100;
vector <int> work[N], on[N];
int n, d, m;

bool bin(int lim) {
    for (int i = 1; i <= n; i++)
        work[i].clear();

    int j = 1, pos = 0, cnt = 0;

    for (int i = 1; i <= n; i++) {
        int cc = 0;
        while (j <= i && cc < lim) {
            if (pos == sz(on[j])) {
                j++;
                pos = 0;
            } else {
                if (i - j > d)
                    return 0;

                work[i].pb(on[j][pos]);
                pos++;
                cnt++;
                cc++;
            }
        }
    }

    if (cnt < m)
        return 0;

    return 1;
}

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> d >> m;

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

    int l = 1, r = m, ans = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (bin(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    bin(ans);

    cout << ans << '\n';

    for (int i = 1; i <= n; i++) {
        for (auto x : work[i])
            cout << x << " ";

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

    return 0;
} 

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	6620 KB	Output is correct
2	Correct	17 ms	6620 KB	Output is correct
3	Correct	15 ms	6872 KB	Output is correct
4	Correct	17 ms	6616 KB	Output is correct
5	Correct	18 ms	6620 KB	Output is correct
6	Correct	16 ms	6620 KB	Output is correct
7	Correct	15 ms	6620 KB	Output is correct
8	Correct	17 ms	6620 KB	Output is correct
9	Correct	23 ms	7004 KB	Output is correct
10	Correct	22 ms	7080 KB	Output is correct
11	Correct	16 ms	6744 KB	Output is correct
12	Correct	31 ms	8284 KB	Output is correct
13	Correct	45 ms	11172 KB	Output is correct
14	Correct	74 ms	13244 KB	Output is correct
15	Correct	72 ms	14196 KB	Output is correct
16	Correct	104 ms	16216 KB	Output is correct
17	Correct	123 ms	20304 KB	Output is correct
18	Correct	123 ms	19024 KB	Output is correct
19	Correct	143 ms	20048 KB	Output is correct
20	Correct	137 ms	20304 KB	Output is correct