oj.uz

답안 #48456

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
48456 2018-05-13T16:25:57 Z IvanC Job Scheduling (CEOI12_jobs) C++17
100 / 100
 367 ms 14060 KB 
#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

# 결과 실행 시간 메모리 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