oj.uz

답안 #260552

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
260552 2020-08-10T14:05:02 Z kshitij_sodani Job Scheduling (CEOI12_jobs) C++14
100 / 100
 423 ms 16984 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
int n,d;
int m;
vector<int> ac[100001];
bool check(int mid,int xx=0){
	int cur=1;
	int le=mid;
	for(int j=1;j<=n;j++){

		for(auto jj:ac[j]){
			
			if(cur>j+d){
				return false;
			}
			le-=1;
			if(xx){
				cout<<jj+1<<" ";
			}
			if(le==0){
				if(xx){
					cout<<0<<endl;
				}
				cur+=1;
				le=mid;
			}
			
		}
		if(cur==j){
			if(xx){
				cout<<0<<endl;
			}
			cur+=1;
			le=mid;
		}
	}


}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>d>>m;
	for(int i=0;i<m;i++){
		int bb;
		cin>>bb;
		ac[bb].pb(i);
	}
	int low=1;
	int high=m;
	while(low<high-1){
		int mid=(low+high)/2;
		if(check(mid)){
			high=mid;
		}
		else{
			low=mid;
		}
	}
	int ans=high;
	if(check(low)){
		ans=min(ans,low);
	}
	cout<<ans<<endl;
	check(ans,1);








	return 0;
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

Compilation message

jobs.cpp: In function 'bool check(int, int)':
jobs.cpp:44:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 4092 KB Output is correct
2 Correct 43 ms 4092 KB Output is correct
3 Correct 44 ms 4092 KB Output is correct
4 Correct 43 ms 4092 KB Output is correct
5 Correct 44 ms 4156 KB Output is correct
6 Correct 43 ms 4084 KB Output is correct
7 Correct 43 ms 4084 KB Output is correct
8 Correct 44 ms 4092 KB Output is correct
9 Correct 240 ms 4644 KB Output is correct
10 Correct 239 ms 4344 KB Output is correct
11 Correct 26 ms 4224 KB Output is correct
12 Correct 49 ms 5752 KB Output is correct
13 Correct 71 ms 8056 KB Output is correct
14 Correct 132 ms 9976 KB Output is correct
15 Correct 116 ms 11000 KB Output is correct
16 Correct 185 ms 13688 KB Output is correct
17 Correct 219 ms 15996 KB Output is correct
18 Correct 223 ms 15712 KB Output is correct
19 Correct 423 ms 16984 KB Output is correct
20 Correct 241 ms 16120 KB Output is correct