Submission #874543

#	Time	Username	Problem	Language	Result	Execution time	Memory
874543		vjudge1	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	276 ms	14784 KiB

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 (stderr)

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 / 100