Submission #706438

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
706438	2023-03-06T14:58:16 Z	chanhchuong123	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	229 ms	14512 KB

jobs

#include <bits/stdc++.h>
using namespace std;
#define task ""
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (b), _a = (a); i >= _a; --i)

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

const int MAX = 1001000;
int n, D, m;
pair<int, int> a[MAX];

bool ok(int x) {
    for (int day = 1, i = 1; day <= n; ++day) {
        if (a[i].fi > day) continue;
        int j = i, r = min(m, i + x - 1);
        while (j <= r && a[j].fi <= day) {
            if (a[i].fi + D < day) return false;
            ++j; if (j == m + 1) return true;
        }
        i = j;
    }
    return false;
}

void trace(int x) {
    for (int day = 1, i = 1; day <= n; ++day) {
        if (a[i].fi > day) {
            cout << "0\n";
            continue;
        }
        int j = i, r = min(m, i + x - 1);
        while (j <= r && a[j].fi <= day) {
            cout << a[j].se << ' ';
            ++j;
        }
        cout << "0\n";
        i = j;
    }
}

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

	if (fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}

    cin >> n >> D >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> a[i].fi;
        a[i].se = i;
    }
    sort(a + 1, a + 1 + m);
    int l = 0, r = 1000000;
    while (r - l > 1) {
        int mid = l + r >> 1;
        if (ok(mid)) r = mid;
        else l = mid;
    }
    cout << r << '\n';
    trace(r);
	return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:68:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |         int mid = l + r >> 1;
      |                   ~~^~~
jobs.cpp:56:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:57:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	1932 KB	Output is correct
2	Correct	16 ms	1996 KB	Output is correct
3	Correct	18 ms	1996 KB	Output is correct
4	Correct	16 ms	2004 KB	Output is correct
5	Correct	21 ms	2004 KB	Output is correct
6	Correct	18 ms	1996 KB	Output is correct
7	Correct	16 ms	1996 KB	Output is correct
8	Correct	18 ms	1936 KB	Output is correct
9	Correct	27 ms	2016 KB	Output is correct
10	Correct	26 ms	2116 KB	Output is correct
11	Correct	25 ms	1996 KB	Output is correct
12	Correct	50 ms	3716 KB	Output is correct
13	Correct	73 ms	5212 KB	Output is correct
14	Correct	105 ms	6816 KB	Output is correct
15	Correct	133 ms	8200 KB	Output is correct
16	Correct	160 ms	9764 KB	Output is correct
17	Correct	184 ms	11192 KB	Output is correct
18	Correct	203 ms	12728 KB	Output is correct
19	Correct	229 ms	14512 KB	Output is correct
20	Correct	185 ms	11316 KB	Output is correct