Submission #48456

#	Time	Username	Problem	Language	Result	Execution time	Memory
48456		IvanC	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	367 ms	14060 KiB

jobs

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;

vector<ii> pares;
int N,D,M;

int checa(int X){
	
	int disponivel = X;
	int dia = 1;
	
	for(int i = 0;i<M;i++){
		if(disponivel == 0){
			dia++;
			disponivel = X;
		}
		while(dia < pares[i].first){
			dia++;
			disponivel = X;
		}
		if(pares[i].first + D < dia) return 0;
		disponivel--;
	}

	return 1;
}

int main(){
	scanf("%d %d %d",&N,&D,&M);
	
	for(int i = 1;i<=M;i++){
		int x;
		scanf("%d",&x);
		pares.push_back(ii(x,i));
	}

	sort(pares.begin(),pares.end());

	int ini = 1,fim = M,meio,resp;
	while(ini <= fim){
		meio = ini + (fim - ini)/2;
		if(checa(meio)){
			resp = meio;
			fim = meio - 1;
		}
		else{
			ini = meio + 1;
		}
	}

	printf("%d\n",resp);

	int disponivel = resp,dia = 1;
	for(int i = 0;i<M;i++){
		if(disponivel == 0){
			printf("0\n");
			disponivel = resp;
			dia++;
		}
		while(dia < pares[i].first){
			printf("0\n");
			disponivel = resp;
			dia++;
		}
		printf("%d ",pares[i].second);
		disponivel--;
	}
	while(dia <= N){
		printf("0\n");
		dia++;
	}
	return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&N,&D,&M);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
jobs.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~
jobs.cpp:57:3: warning: 'resp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(disponivel == 0){
   ^~

• Subtask 1: 100 / 100