Submission #726787

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
726787	2023-04-19T11:18:41 Z	penguin133	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	320 ms	20968 KB

jobs

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, d, m;
pi A[1000005];

void solve(){
	cin >> n >> d >> m;
	for(int i=1;i<=m;i++)cin >> A[i].fi, A[i].se = i;
	sort(A+1, A+m+1);
	int lo = 0, hi = m, ans = m;
	while(lo <= hi){
		int mid = (lo + hi) >> 1;
		int in = 1;
		deque <int> dq;
		bool f = 1;
		for(int i=1;i<=n;i++){
			while(in <= m && A[in].fi == i)dq.push_back(A[in++].fi);
			for(int j=1;j<=mid;j++){
				if(dq.empty())break;
				dq.pop_front();
			}
			if(!dq.empty() && dq.front() + d <= i)f = 0;
		}
		if(f)ans = mid, hi = mid - 1;
		else lo = mid + 1;
	}
	cout << ans << '\n';
	int in = 1;
	deque <int> dq;
	for(int i=1;i<=n;i++){
		while(in <= m && A[in].fi == i)dq.push_back(A[in++].se);
		for(int j=1;j<=ans;j++){
			if(dq.empty())break;
			cout << dq.front() << ' ';
			dq.pop_front();
		}
		cout << "0\n";
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

jobs.cpp:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main(){
      | ^~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	3280 KB	Output is correct
2	Correct	26 ms	3388 KB	Output is correct
3	Correct	28 ms	3252 KB	Output is correct
4	Correct	29 ms	3308 KB	Output is correct
5	Correct	26 ms	3368 KB	Output is correct
6	Correct	26 ms	3348 KB	Output is correct
7	Correct	27 ms	3256 KB	Output is correct
8	Correct	24 ms	3500 KB	Output is correct
9	Correct	37 ms	2696 KB	Output is correct
10	Correct	45 ms	2808 KB	Output is correct
11	Correct	31 ms	2460 KB	Output is correct
12	Correct	55 ms	4940 KB	Output is correct
13	Correct	94 ms	7116 KB	Output is correct
14	Correct	124 ms	9608 KB	Output is correct
15	Correct	147 ms	11556 KB	Output is correct
16	Correct	189 ms	14180 KB	Output is correct
17	Correct	225 ms	16552 KB	Output is correct
18	Correct	253 ms	18432 KB	Output is correct
19	Correct	320 ms	20968 KB	Output is correct
20	Correct	222 ms	16636 KB	Output is correct