Submission #874543

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
874543	2023-11-17T08:12:22 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	276 ms	14784 KB

jobs

#include <bits/stdc++.h>
#define pb push_back
#define dbg(x) cout << "reached here " << x << endl;
#define f first
#define s second
#define ll long long

using namespace std;
typedef pair<int, int> pii;

const int maxn = 1e5+5;
int n, m, d;
int cnt[maxn], tme[20*maxn];
vector<int> job;

bool check(int mid)
{
	set<pii> q;
	for (int i = 1; i <= n; ++i)
		if(cnt[i])
			q.insert(pii(i, cnt[i]));

	int t = 1;
	while(q.size())
	{
		int h = mid;
		if((*q.begin()).f > t){t++; continue;}
		if(t > (*q.begin()).f + d) return false;

		while(h and (*q.begin()).f <= t and q.size())
		{
			int v = (*q.begin()).s, u = (*q.begin()).f;
			int w = min(h, v);
			v -= w;
			h -= w;

			q.erase(q.begin());
			if(v)
				q.insert(pii(u, v));
		}

		t++;
	}

	return true;
}

bool cmp(int x, int y) {return tme[x] < tme[y];}	

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

	cin >> n >> d >> m;

	for (int i = 1; i <= m; ++i)
	{
		int a;
		cin >> a;

		cnt[a]++;
		job.pb(i);
		tme[i] = a;
	}

	int l = 1, r = m+1;
	while(r-l > 1)
	{
		int mid = (l+r)/2;

		if(check(mid))
			r = mid;
		else
			l = mid;
	}

	cout << r << endl;
	sort(job.begin(), job.end(), cmp);

	int p = r, t = 1; 
	for (int i = 0; i < job.size(); ++i)
	{
		if(!p or t < tme[job[i]])
		{
			cout << 0 << endl;
			p = r;
			t++;
		}

		cout << job[i] << ' ';
		p--;
	}	

	for (int i = t; i <= n; ++i)
		cout << 0 << endl;
		

	return 0;
} 

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:83:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for (int i = 0; i < job.size(); ++i)
      |                  ~~^~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	3800 KB	Output is correct
2	Correct	23 ms	3800 KB	Output is correct
3	Correct	23 ms	3804 KB	Output is correct
4	Correct	27 ms	3792 KB	Output is correct
5	Correct	23 ms	3804 KB	Output is correct
6	Correct	24 ms	3800 KB	Output is correct
7	Correct	24 ms	3800 KB	Output is correct
8	Correct	24 ms	3804 KB	Output is correct
9	Correct	123 ms	3848 KB	Output is correct
10	Correct	123 ms	3804 KB	Output is correct
11	Correct	21 ms	3792 KB	Output is correct
12	Correct	40 ms	5076 KB	Output is correct
13	Correct	66 ms	5828 KB	Output is correct
14	Correct	114 ms	7272 KB	Output is correct
15	Correct	101 ms	8392 KB	Output is correct
16	Correct	158 ms	11720 KB	Output is correct
17	Correct	182 ms	13844 KB	Output is correct
18	Correct	163 ms	13588 KB	Output is correct
19	Correct	276 ms	14784 KB	Output is correct
20	Correct	180 ms	14016 KB	Output is correct