Submission #977263

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
977263	2024-05-07T15:20:45 Z	LOLOLO	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	1000 ms	28500 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];
int n, d;

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

    priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> pq;
    for (int i = 1; i <= n; i++) {
        for (auto x : on[i]) {
            pq.push({i, x});
        }

        for (int j = 1; j <= lim; j++) {
            if (pq.empty())
                break;

            auto t = pq.top();
            if (i - t.f > d)
                return 0;

            work[i].pb(t.s);
            pq.pop();
        }
    }

    if (sz(pq))
        return 0;

    return 1;
}

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

    int m;
    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

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	141 ms	13120 KB	Output is correct
2	Correct	142 ms	13264 KB	Output is correct
3	Correct	142 ms	13120 KB	Output is correct
4	Correct	142 ms	13116 KB	Output is correct
5	Correct	145 ms	13116 KB	Output is correct
6	Correct	144 ms	13168 KB	Output is correct
7	Correct	142 ms	13324 KB	Output is correct
8	Correct	144 ms	13120 KB	Output is correct
9	Correct	123 ms	12008 KB	Output is correct
10	Correct	130 ms	12180 KB	Output is correct
11	Correct	71 ms	11856 KB	Output is correct
12	Correct	247 ms	13988 KB	Output is correct
13	Correct	298 ms	17232 KB	Output is correct
14	Correct	370 ms	20896 KB	Output is correct
15	Correct	426 ms	20824 KB	Output is correct
16	Correct	353 ms	23892 KB	Output is correct
17	Correct	562 ms	28500 KB	Output is correct
18	Execution timed out	1038 ms	27120 KB	Time limit exceeded
19	Execution timed out	1034 ms	28344 KB	Time limit exceeded
20	Correct	549 ms	28500 KB	Output is correct