Submission #1084306

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1084306	2024-09-05T20:01:28 Z	4QT0R	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	105 ms	20560 KB

jobs

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

int zle[100003];
int wej[1000003];
vector<int> ans[100003];

deque<pair<int,int>> dq;
queue<int> q;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n,d,m;
	cin >> n >> d >> m;
	for (int i = 1; i<=m; i++){
		cin >> wej[i];
		zle[wej[i]]++;
		ans[wej[i]].push_back(i);
	}
	int l=1,p=m,md;
	while(l<p){
		md=(l+p)/2;
		bool ok=true;
		for (int i = 1; i<=n; i++){
			dq.push_back({zle[i],i});
			int lft=md;
			while(dq.size() && lft){
				auto [z,ind] = dq.front();
				dq.pop_front();
				if (lft>=z){
					lft-=z;
					z=0;
				}
				else{
					z-=lft;
					lft=0;
					dq.push_front({z,ind});
				}
			}
			if (dq.size() && dq.front().second+d<=i){
				ok=false;
				dq.clear();
				break;
			}
		}
		if (dq.size())ok=false;
		dq.clear();
		if (ok)p=md;
		else l=md+1;
	}
	cout << l << '\n';
	for (int i = 1; i<=n; i++){
		for (auto u : ans[i])q.push(u);
		for (int j = 1; j<=l; j++){
			if (q.empty())break;
			cout << q.front() << ' ';
			q.pop();
		}
		cout << "0\n";
	}
}

Subtask #1

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	4828 KB	Output is correct
2	Correct	11 ms	4828 KB	Output is correct
3	Correct	11 ms	4828 KB	Output is correct
4	Correct	12 ms	4828 KB	Output is correct
5	Correct	13 ms	4824 KB	Output is correct
6	Correct	11 ms	4828 KB	Output is correct
7	Correct	11 ms	4828 KB	Output is correct
8	Correct	13 ms	4752 KB	Output is correct
9	Correct	17 ms	4700 KB	Output is correct
10	Correct	18 ms	4700 KB	Output is correct
11	Correct	13 ms	4696 KB	Output is correct
12	Incorrect	27 ms	6480 KB	Output isn't correct
13	Correct	33 ms	9300 KB	Output is correct
14	Incorrect	56 ms	11600 KB	Output isn't correct
15	Correct	71 ms	12880 KB	Output is correct
16	Correct	84 ms	16036 KB	Output is correct
17	Correct	89 ms	18772 KB	Output is correct
18	Correct	91 ms	18772 KB	Output is correct
19	Correct	105 ms	20560 KB	Output is correct
20	Correct	91 ms	18824 KB	Output is correct