Submission #1219075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219075		Bui_Quoc_Cuong	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	656 ms	30540 KiB

jobs

#include <bits/stdc++.h>
#define ALL(A) (A).begin(), (A).end()
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define FOR(i, a, b) for(int i = a; i <= (int)b; i++)
#define FORD(i, a, b) for(int i = a; i >= (int)b; i--)
#define file(ko) if(fopen(ko".inp", "r")){freopen(ko".inp", "r", stdin);freopen(ko".out", "w", stdout);}
using namespace std;
const int N = 1e6 + 5;

int n, d, m;
struct bg{
	int l, r, id;
} a[N];
vector <int> open[(int)1e5 + 5], res[(int)1e5 + 5];

bool check(int mid) {
	#define bg array <int, 2>
	priority_queue <bg, vector <bg>, greater <bg>> pq;

	FOR(i, 1, n) {
		for (int &id : open[i]) {
			pq.push({a[id].r, i});
		}
		int cnt = mid;
		while (!pq.empty() && cnt > 0) {
			int u = pq.top()[0]; pq.pop();
			if (u < i) return 0;
			cnt--;
		}
	}

	return (pq.empty());
}

void process() {
	cin >> n >> d >> m;
	FOR(i, 1, m) cin >> a[i].l, a[i].r = a[i].l + d, a[i].id = i;
	FOR(i, 1, m) open[a[i].l].push_back(i);

	int l = 0, r = m, ans = 0;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	cout << ans << "\n";

	priority_queue <bg, vector <bg>, greater <bg>> pq;
	FOR(i, 1, n) {
		for (int &id : open[i]) {
			pq.push({a[id].r, id});
		}
		int cnt = ans;
		while (!pq.empty() && cnt > 0) {
			int id = pq.top()[1];
			pq.pop();
			res[i].push_back(id);
			cnt--;
		}
	}

	FOR(i, 1, n) {
		for (int &id : res[i]) cout << id << " ";
		cout << "0\n";
	}
}   

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); cout.tie(nullptr);
    
    file("kieuoanh");
    process();

    return void(cerr << "\n" << TIME), 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:6:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define file(ko) if(fopen(ko".inp", "r")){freopen(ko".inp", "r", stdin);freopen(ko".out", "w", stdout);}
      |                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:72:5: note: in expansion of macro 'file'
   72 |     file("kieuoanh");
      |     ^~~~
jobs.cpp:6:80: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define file(ko) if(fopen(ko".inp", "r")){freopen(ko".inp", "r", stdin);freopen(ko".out", "w", stdout);}
      |                                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:72:5: note: in expansion of macro 'file'
   72 |     file("kieuoanh");
      |     ^~~~

• Subtask 1: 100 / 100