Submission #50311

#	Time	Username	Problem	Language	Result	Execution time	Memory
50311		MatheusLealV	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	423 ms	43212 KiB

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

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