Submission #977269

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
977269	2024-05-07T15:25:03 Z	LOLOLO	Job Scheduling (CEOI12_jobs)	C++17	85 / 100	208 ms	34392 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 = 2e5 + 100;
vector <int> work[N], on[N], need[N];
int n, d, m;

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

    int j = 1, cnt = 0;

    for (int i = 1; i <= n; i++) {
        for (auto x : on[i]) {
            need[i].pb(x);
        }

        int cc = 0;
        while (j <= i && cc < lim) {
            if (need[j].empty()) {
                j++;
            } else {
                if (i - j > d)
                    return 0;

                work[i].pb(need[j].back());
                need[j].pop_back();
                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

85.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	16556 KB	Output is correct
2	Correct	22 ms	16524 KB	Output is correct
3	Correct	21 ms	16480 KB	Output is correct
4	Correct	21 ms	16576 KB	Output is correct
5	Correct	21 ms	16480 KB	Output is correct
6	Correct	22 ms	16480 KB	Output is correct
7	Correct	21 ms	16476 KB	Output is correct
8	Correct	24 ms	16476 KB	Output is correct
9	Correct	36 ms	16728 KB	Output is correct
10	Correct	31 ms	17008 KB	Output is correct
11	Correct	22 ms	16984 KB	Output is correct
12	Correct	45 ms	18772 KB	Output is correct
13	Correct	60 ms	22612 KB	Output is correct
14	Correct	99 ms	24660 KB	Output is correct
15	Correct	91 ms	26196 KB	Output is correct
16	Correct	131 ms	29012 KB	Output is correct
17	Runtime error	154 ms	34392 KB	Memory limit exceeded
18	Correct	175 ms	32592 KB	Output is correct
19	Runtime error	208 ms	33432 KB	Memory limit exceeded
20	Runtime error	154 ms	34388 KB	Memory limit exceeded