Submission #899573

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
899573	2024-01-06T13:35:24 Z	LCJLY	Job Scheduling (CEOI12_jobs)	C++14	60 / 100	152 ms	20972 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=n;
	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

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	18 ms	4824 KB	Output isn't correct
2	Incorrect	16 ms	4820 KB	Output isn't correct
3	Incorrect	17 ms	4824 KB	Output isn't correct
4	Incorrect	17 ms	4940 KB	Output isn't correct
5	Incorrect	18 ms	4824 KB	Output isn't correct
6	Incorrect	17 ms	4824 KB	Output isn't correct
7	Incorrect	18 ms	4940 KB	Output isn't correct
8	Incorrect	17 ms	4820 KB	Output isn't correct
9	Correct	25 ms	5200 KB	Output is correct
10	Correct	24 ms	5136 KB	Output is correct
11	Correct	17 ms	4576 KB	Output is correct
12	Correct	28 ms	6028 KB	Output is correct
13	Correct	42 ms	9296 KB	Output is correct
14	Correct	74 ms	11252 KB	Output is correct
15	Correct	68 ms	12140 KB	Output is correct
16	Correct	104 ms	14652 KB	Output is correct
17	Correct	133 ms	17664 KB	Output is correct
18	Correct	118 ms	17256 KB	Output is correct
19	Correct	152 ms	20972 KB	Output is correct
20	Correct	127 ms	17792 KB	Output is correct