Submission #706438

#	Time	Username	Problem	Language	Result	Execution time	Memory
706438		chanhchuong123	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	229 ms	14512 KiB

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 (stderr)

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 / 100