Submission #602409

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
602409	2022-07-23T04:19:52 Z	hail	Job Scheduling (CEOI12_jobs)	C++17	50 / 100	691 ms	16980 KB

jobs

#include <bits/stdc++.h>

using namespace std;


#define mp make_pair

int n, d, m;

vector<vector<int>> jobs(1, vector<int>(0));

bool check(int mach)
{
	int day=1;
	int dr=mach;

	int s;
	for(int i=1 ; i<=n; i++)
	{
		s = (int)jobs[i].size();
		if(day<i) {day=i; dr=mach;}
		if(s>dr) {s-=dr; day++; dr=mach;}
		else { dr-=s; s = 0; continue;}
		if(dr==0) {day++; dr=mach;}
		day += s/mach;
		dr = mach - (s%mach);
		if(day>i+d || day>n) return false;
	}
	return true;
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	
	cin>>n>>d>>m;

	jobs.resize(n+1);
	int o;

	for(int i=1; i<=m; i++)
	{
		cin>>o;
		jobs[o].push_back(i);
	}

	int high = 100000001;
	int low = 0;
	int mid;
	while(high-low>1)
	{
		mid = (high+low)/2;
		if(check(mid)) high = mid;
		else low = mid;
	}

	cout<<high<<"\n";

	int num_mach = high;
	int curr=1;
	int cnt=0;
	for(int i = 1; i<=n ; i++)
	{
		cnt = 0;
		while((cnt<num_mach))
		{
			if(jobs[curr].empty())
			{
				while((jobs[curr].empty()) && curr<=i)
				{
					curr++;
				}
				if(curr>i)
				{
					cout<<0<<"\n";
					cnt=0;
					break;
				}
			}
			cout<<jobs[curr][0]<<" ";
			jobs[curr].erase(jobs[curr].begin());
			cnt++;
		}
		if(cnt==num_mach) cout<<0<<"\n";
	}

}

Subtask #1

50.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	691 ms	1860 KB	Output isn't correct
2	Incorrect	671 ms	1984 KB	Output isn't correct
3	Incorrect	625 ms	1952 KB	Output isn't correct
4	Incorrect	624 ms	1960 KB	Output isn't correct
5	Incorrect	627 ms	1904 KB	Output isn't correct
6	Incorrect	619 ms	1868 KB	Output isn't correct
7	Incorrect	630 ms	1976 KB	Output isn't correct
8	Incorrect	617 ms	1896 KB	Output isn't correct
9	Correct	58 ms	4264 KB	Output is correct
10	Correct	46 ms	4336 KB	Output is correct
11	Correct	17 ms	1876 KB	Output is correct
12	Incorrect	32 ms	3344 KB	Output isn't correct
13	Correct	49 ms	5660 KB	Output is correct
14	Incorrect	80 ms	7732 KB	Output isn't correct
15	Correct	100 ms	8644 KB	Output is correct
16	Correct	109 ms	11440 KB	Output is correct
17	Correct	128 ms	13884 KB	Output is correct
18	Correct	173 ms	13540 KB	Output is correct
19	Correct	175 ms	16980 KB	Output is correct
20	Correct	128 ms	13784 KB	Output is correct