Submission #48456

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
48456	2018-05-13T16:25:57 Z	IvanC	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	367 ms	14060 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	1900 KB	Output is correct
2	Correct	31 ms	2024 KB	Output is correct
3	Correct	29 ms	2024 KB	Output is correct
4	Correct	33 ms	2024 KB	Output is correct
5	Correct	30 ms	2128 KB	Output is correct
6	Correct	29 ms	2128 KB	Output is correct
7	Correct	29 ms	2128 KB	Output is correct
8	Correct	28 ms	2128 KB	Output is correct
9	Correct	43 ms	2152 KB	Output is correct
10	Correct	42 ms	2244 KB	Output is correct
11	Correct	42 ms	2244 KB	Output is correct
12	Correct	82 ms	3584 KB	Output is correct
13	Correct	123 ms	4988 KB	Output is correct
14	Correct	218 ms	6504 KB	Output is correct
15	Correct	209 ms	7908 KB	Output is correct
16	Correct	260 ms	9432 KB	Output is correct
17	Correct	304 ms	11024 KB	Output is correct
18	Correct	332 ms	12392 KB	Output is correct
19	Correct	367 ms	14060 KB	Output is correct
20	Correct	289 ms	14060 KB	Output is correct