Submission #50311

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
50311	2018-06-10T03:18:00 Z	MatheusLealV	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	423 ms	43212 KB

jobs

#include <bits/stdc++.h>
#define N 100050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, d, m, day[10*N];

vector<int> v[N], ans[N];

int atendido[N];

bool solve(int k)
{
	queue<int> fila;

	for(int dia = 1; dia <= n; dia ++)
	{
		for(auto x: v[dia]) fila.push(x);

		int cnt = 0;

		while(!fila.empty() and day[fila.front()] + d >= dia and cnt < k)
		{
			cnt ++;

			fila.pop();
		}
	}

	return fila.empty();
}

void solve2(int k)
{
	queue<int> fila;

	for(int dia = 1; dia <= n; dia ++)
	{
		for(auto x: v[dia]) fila.push(x);

		int cnt = 0;

		while(!fila.empty() and day[fila.front()] + d >= dia and cnt < k)
		{
			cout<<fila.front()<<" ";

			cnt ++;

			fila.pop();
		}

		cout<<"0\n";
	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>d>>m;

	for(int i = 1, di; i <= m; i++)
	{
		cin>>day[i];

		v[day[i]].push_back(i);
	}

	int ini = 1, fim = m, mid, best;

	while(fim >= ini)
	{
		mid = (ini + fim)/2;

		if(solve(mid)) fim = mid - 1, best = mid;

		else ini = mid + 1;
	}

	cout<<best<<"\n";

	solve2(best);
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:64:17: warning: unused variable 'di' [-Wunused-variable]
  for(int i = 1, di; i <= m; i++)
                 ^~
jobs.cpp:82:14: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout<<best<<"\n";
              ^~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	7124 KB	Output is correct
2	Correct	36 ms	7604 KB	Output is correct
3	Correct	36 ms	7784 KB	Output is correct
4	Correct	37 ms	8096 KB	Output is correct
5	Correct	36 ms	8532 KB	Output is correct
6	Correct	37 ms	8752 KB	Output is correct
7	Correct	39 ms	9084 KB	Output is correct
8	Correct	36 ms	9500 KB	Output is correct
9	Correct	41 ms	9772 KB	Output is correct
10	Correct	43 ms	10040 KB	Output is correct
11	Correct	43 ms	10244 KB	Output is correct
12	Correct	71 ms	12556 KB	Output is correct
13	Correct	170 ms	15876 KB	Output is correct
14	Correct	190 ms	19396 KB	Output is correct
15	Correct	170 ms	22664 KB	Output is correct
16	Correct	252 ms	27600 KB	Output is correct
17	Correct	318 ms	33156 KB	Output is correct
18	Correct	305 ms	36648 KB	Output is correct
19	Correct	423 ms	41460 KB	Output is correct
20	Correct	374 ms	43212 KB	Output is correct