답안 #899574

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
899574 2024-01-06T13:36:06 Z LCJLY Job Scheduling (CEOI12_jobs) C++14
100 / 100
163 ms 18080 KB
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<int,int>pii;
//typedef pair<int,pii>pi2;
typedef array<int,4>pi2;

void solve(){	
	int n,m,k;
	cin >> n >> m >> k;
	
	vector<int>arr[100005];
	int temp;
	for(int x=0;x<k;x++){
		cin >>	temp;
		arr[temp].push_back(x+1);
	}
	
	int l=0;
	int r=k;
	int best=r;
	int mid;
	
	while(l<=r){
		mid=(l+r)/2;
		
		queue<int>q;
		bool amos=true;
		
		for(int x=1;x<=n;x++){
			for(auto it:arr[x]){
				q.push(x);
			}
				
			for(int y=0;y<mid;y++){
				if(q.empty()) break;
				if(x-q.front()>m) amos=false;
				q.pop();
			}
		}
		
		if(amos){
			best=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	
	cout << best << "\n";
	
	queue<int>qq;
	for(int x=1;x<=n;x++){
		for(auto it:arr[x]){
			qq.push(it);
		}
		
		//show2(x,x,arr[x].size(),arr[x].size());
		
		for(int y=0;y<best;y++){
			if(qq.empty()) break;
			cout << qq.front() << " ";
			qq.pop();
		}
		
		cout << 0 << "\n";
	}
}
 
int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	//freopen("redistricting.in", "r", stdin);
	//freopen("redistricting.out", "w", stdout);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}	
}

Compilation message

jobs.cpp: In function 'void solve()':
jobs.cpp:37:13: warning: unused variable 'it' [-Wunused-variable]
   37 |    for(auto it:arr[x]){
      |             ^~
# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 4820 KB Output is correct
2 Correct 19 ms 4936 KB Output is correct
3 Correct 19 ms 4824 KB Output is correct
4 Correct 18 ms 4820 KB Output is correct
5 Correct 19 ms 4820 KB Output is correct
6 Correct 19 ms 4824 KB Output is correct
7 Correct 20 ms 4836 KB Output is correct
8 Correct 20 ms 4824 KB Output is correct
9 Correct 26 ms 4944 KB Output is correct
10 Correct 26 ms 4876 KB Output is correct
11 Correct 19 ms 4444 KB Output is correct
12 Correct 34 ms 5980 KB Output is correct
13 Correct 51 ms 9044 KB Output is correct
14 Correct 85 ms 10952 KB Output is correct
15 Correct 83 ms 12120 KB Output is correct
16 Correct 126 ms 14816 KB Output is correct
17 Correct 145 ms 17784 KB Output is correct
18 Correct 140 ms 16976 KB Output is correct
19 Correct 163 ms 18080 KB Output is correct
20 Correct 138 ms 17784 KB Output is correct