Submission #377665

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
377665	2021-03-14T16:27:33 Z	vishesh312	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	348 ms	13932 KB

jobs

#include "bits/stdc++.h"
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
*/

#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()

using ll = long long;
const int mod = 1e9+7;

vector<array<int, 2>> v;
int n, m, d;

bool chk(int x) {
    int k = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < x and k < m; ++j) {
            if (i > v[k][0] + d) return false;
            if (i >= v[k][0]) ++k;
            else break;
        }
    }
    return 1;
}

void solve(int tc) {
    cin >> n >> d >> m;
    v.resize(m);
    for (int i = 0; i < m; ++i) {
        cin >> v[i][0];
        v[i][1] = i;
    }
    sort(all(v));
    int lo = 1, hi = m+1;
    int ans;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
//      cout << "mid : " << mid << '\n';
        if (chk(mid)) {
            ans = mid;
            hi = mid;
        } else lo = mid + 1;
    }
    cout << ans << '\n';
    int x = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < ans and x < m; ++j) {
            cout << v[x++][1] + 1 << " ";
        }
        cout << "0\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int tc = 1;
    //cin >> tc;
    for (int i = 1; i <= tc; ++i) solve(i);
    return 0;
}

Compilation message

jobs.cpp: In function 'void solve(int)':
jobs.cpp:39:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |     int ans;
      |         ^~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	1772 KB	Output is correct
2	Correct	29 ms	1772 KB	Output is correct
3	Correct	25 ms	1772 KB	Output is correct
4	Correct	24 ms	1772 KB	Output is correct
5	Correct	24 ms	1772 KB	Output is correct
6	Correct	25 ms	1772 KB	Output is correct
7	Correct	25 ms	1772 KB	Output is correct
8	Correct	25 ms	1772 KB	Output is correct
9	Correct	37 ms	1900 KB	Output is correct
10	Correct	36 ms	1900 KB	Output is correct
11	Correct	32 ms	1772 KB	Output is correct
12	Correct	67 ms	3180 KB	Output is correct
13	Correct	98 ms	4716 KB	Output is correct
14	Correct	138 ms	6252 KB	Output is correct
15	Correct	165 ms	7660 KB	Output is correct
16	Correct	221 ms	9196 KB	Output is correct
17	Correct	245 ms	10732 KB	Output is correct
18	Correct	276 ms	12160 KB	Output is correct
19	Correct	348 ms	13932 KB	Output is correct
20	Correct	243 ms	10732 KB	Output is correct