Submission #743260

#	Time	Username	Problem	Language	Result	Execution time	Memory
743260		NintsiChkhaidze	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	495 ms	26144 KiB

jobs

#include <bits/stdc++.h>
#define ll long long
#define s second
#define pb push_back
#define f first
using namespace std;
 
const int N = 1e5 + 5;
pair <int,int> a[1000005];
vector <int> v[N],ans[N];
int n,m,d;
 
bool check(int x){
	int l = 1;
	for (int i = 1; i <= n; i++){
		v[i].clear();
		while (l <= m && a[l].f <= i && i - a[l].f <= d && v[i].size() < x){
			v[i].pb(a[l].s);
			++l;
		}
	}
	if (l != m + 1) return 0;
	
	for (int i = 1; i <= n; i++){
		ans[i] = v[i];
	}
	return 1; 
}
signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    
    cin>>n>>d>>m;
    
	for (int i = 1; i <= m; i++){
		cin>>a[i].f;
		a[i].s = i;
	}
	sort(a+1,a+m+1);
	
	int l = 1, r = m,res=0;
	while (l <= r){
		int mid = (l + r)>>1;
		if (check(mid)){
			res=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	cout<<res<<endl;
	for (int i = 1; i <= n; i++){
		for (int x: v[i]) cout<<x<<" ";
		cout<<0<<endl;
	}
}
 
/*
8 2 12 
1 2 4 2 1 3 5 6 2 3 6 4 
*/

Compilation message (stderr)

jobs.cpp: In function 'bool check(int)':
jobs.cpp:17:66: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   17 |   while (l <= m && a[l].f <= i && i - a[l].f <= d && v[i].size() < x){
      |                                                      ~~~~~~~~~~~~^~~

• Subtask 1: 100 / 100