Submission #899574

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
899574	2024-01-06T13:36:06 Z	LCJLY	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	163 ms	18080 KB

jobs

#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]){
      |             ^~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	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