Submission #1062292

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1062292	2024-08-17T01:55:41 Z	Kiet07	Job Scheduling (CEOI12_jobs)	C++14	60 / 100	1000 ms	65536 KB

jobs

#include<bits/stdc++.h>
using namespace std;
int n,m,d;
bool check(int x,multiset<pair<int,int>>ms)
{
	for(int days=1;days<=n;days++)
	{
		for(int i=1;i<=x;i++)
		{
			if(days<=ms.begin()->first+d)
			{
				if(days>=ms.begin()->first)
				{
					ms.erase(ms.begin());
					if(ms.empty())
					{
						return true;
					}
				}
			}
			else
			{
				return false;
			}
		}
	}
	if(ms.empty())
	{
		return true;
	}
	else
	{
		return false;
	}
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//freopen("TEST.inp","r",stdin);
	cin>>n>>d>>m;
	multiset<pair<int,int>>ms;
	for(int i=1;i<=m;i++)
	{
		int x; cin>>x;
		ms.insert({x,i});
	}
	int l=1,r=1000000,ans=r;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(check(mid,ms))
		{
			ans=mid;
			r=mid-1;
		}
		else
		{
			l=mid+1;
		}
	}
	cout<<ans<<'\n';
	for(int days=1;days<=n;days++)
	{
		if(!ms.empty())
		{
			for(int i=1;i<=ans;i++)
			{
				if(days>=ms.begin()->first&&days<=ms.begin()->first+d)
				{
					cout<<ms.begin()->second<<' ';
					ms.erase(ms.begin());
					if(ms.empty())
					{
						break;
					}
				}
			}
		}
		cout<<0<<'\n';
	}
	return 0;
}

Subtask #1

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	10324 KB	Output is correct
2	Correct	99 ms	10352 KB	Output is correct
3	Correct	113 ms	10388 KB	Output is correct
4	Correct	131 ms	10320 KB	Output is correct
5	Correct	141 ms	10320 KB	Output is correct
6	Correct	153 ms	10324 KB	Output is correct
7	Correct	171 ms	10352 KB	Output is correct
8	Correct	198 ms	10340 KB	Output is correct
9	Correct	103 ms	10544 KB	Output is correct
10	Correct	104 ms	10580 KB	Output is correct
11	Correct	824 ms	10336 KB	Output is correct
12	Correct	869 ms	20380 KB	Output is correct
13	Execution timed out	1046 ms	28480 KB	Time limit exceeded
14	Execution timed out	1071 ms	37972 KB	Time limit exceeded
15	Execution timed out	1083 ms	47208 KB	Time limit exceeded
16	Execution timed out	1018 ms	56656 KB	Time limit exceeded
17	Runtime error	400 ms	65536 KB	Execution killed with signal 9
18	Runtime error	467 ms	65536 KB	Execution killed with signal 9
19	Runtime error	501 ms	65536 KB	Execution killed with signal 9
20	Runtime error	410 ms	65536 KB	Execution killed with signal 9