Submission #874535

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
874535	2023-11-17T07:58:54 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	696 ms	15548 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));
		}
	}

	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:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for (int i = 0; i < job.size(); ++i)
      |                  ~~^~~~~~~~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	70 ms	3872 KB	Output isn't correct
2	Incorrect	73 ms	3816 KB	Output isn't correct
3	Incorrect	70 ms	3792 KB	Output isn't correct
4	Incorrect	70 ms	3788 KB	Output isn't correct
5	Incorrect	70 ms	3792 KB	Output isn't correct
6	Incorrect	70 ms	3696 KB	Output isn't correct
7	Incorrect	75 ms	3648 KB	Output isn't correct
8	Incorrect	70 ms	3792 KB	Output isn't correct
9	Incorrect	130 ms	3792 KB	Output isn't correct
10	Incorrect	132 ms	3796 KB	Output isn't correct
11	Incorrect	77 ms	3732 KB	Output isn't correct
12	Incorrect	155 ms	4924 KB	Output isn't correct
13	Incorrect	238 ms	6048 KB	Output isn't correct
14	Incorrect	329 ms	7620 KB	Output isn't correct
15	Incorrect	402 ms	8464 KB	Output isn't correct
16	Incorrect	525 ms	13628 KB	Output isn't correct
17	Incorrect	576 ms	14268 KB	Output isn't correct
18	Incorrect	621 ms	14148 KB	Output isn't correct
19	Incorrect	696 ms	15548 KB	Output isn't correct
20	Incorrect	590 ms	14808 KB	Output isn't correct