Submission #602611

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
602611	2022-07-23T09:25:49 Z	hail	Job Scheduling (CEOI12_jobs)	C++17	50 / 100	667 ms	16968 KB

jobs

#include <bits/stdc++.h>

using namespace std;

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;
			if(dr==0)
			{
				day++;
				dr=mach;
			}
			continue;
		}
		day += s/mach;
		dr = mach - (s%mach);
		if(dr == 0) {day++; dr = 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 = 1000001;
	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++;
					if(curr>i) break;
				}
				if(curr>i || curr>n-d)
				{
					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	666 ms	1888 KB	Output isn't correct
2	Incorrect	667 ms	1864 KB	Output isn't correct
3	Incorrect	639 ms	2084 KB	Output isn't correct
4	Incorrect	652 ms	2028 KB	Output isn't correct
5	Incorrect	612 ms	1860 KB	Output isn't correct
6	Incorrect	643 ms	1924 KB	Output isn't correct
7	Incorrect	629 ms	2028 KB	Output isn't correct
8	Incorrect	626 ms	1956 KB	Output isn't correct
9	Correct	45 ms	4244 KB	Output is correct
10	Correct	52 ms	4332 KB	Output is correct
11	Correct	16 ms	1864 KB	Output is correct
12	Incorrect	44 ms	3312 KB	Output isn't correct
13	Correct	52 ms	5608 KB	Output is correct
14	Incorrect	83 ms	7740 KB	Output isn't correct
15	Correct	92 ms	8668 KB	Output is correct
16	Correct	125 ms	11504 KB	Output is correct
17	Correct	133 ms	13864 KB	Output is correct
18	Correct	145 ms	13580 KB	Output is correct
19	Correct	204 ms	16968 KB	Output is correct
20	Correct	128 ms	13836 KB	Output is correct