Submission #439490

#	Time	Username	Problem	Language	Result	Execution time	Memory
439490		sksusha8853	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	474 ms	25804 KiB

jobs

#include<bits/stdc++.h>
using namespace std;
#define ll   long long int
int mod=1000000007;
bool check(vector<int>&a,int n,int d,int m,int M){
	vector<int>v1(n+1,0);
	int z=n;
	for(int i=m;i>=1;i--){
		if(v1[z]==M){
			z--;
		}
		z=min(z,a[i]+d);
		
		if(z<a[i]){
			return false;
			
		}
		else
		v1[z]++;
		
	}
	return true;
}

void solve(){
	int n,d,m;
	cin>>n>>d>>m;
	vector<int>a(m+1);
	vector<pair<int,int>>b(m+1);
	int x,y;
	for(int i=1;i<=m;i++){
		cin>>x;
		a[i]=x;
		b[i]=make_pair(x,i);
		
	}
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	int i=1,j=m;
	int ans=0;
	while(i<=j){
		int M=(i+j)/2;
		if(check(a,n,d,m,M)){
			ans=M;
			j=M-1;
		}
		else
		i=M+1;
	}
	cout<<ans<<'\n';
	vector<vector<int>>adj(n+1);
	int z=n;
	for(int i=m;i>=1;i--){
		if(adj[z].size()==ans){
			z--;
		}
		z=min(z,b[i].first+d);
		adj[z].push_back(b[i].second);
		
		
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<adj[i].size();j++){
			cout<<adj[i][j]<<' ';
		}
		cout<<0<<'\n';
	}


}
int main()
{ios_base::sync_with_stdio(false);cin.tie(0);cin.tie(0);
	//freopen("SKS.in", "r", stdin);
  //freopen("SKS.out", "w", stdout);
	 int t=1;
	 //cin>>t;
	 while(t--)solve();
	 
return 0;}

Compilation message (stderr)

jobs.cpp: In function 'void solve()':
jobs.cpp:54:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |   if(adj[z].size()==ans){
      |      ~~~~~~~~~~~~~^~~~~
jobs.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int j=0;j<adj[i].size();j++){
      |               ~^~~~~~~~~~~~~~
jobs.cpp:30:8: warning: unused variable 'y' [-Wunused-variable]
   30 |  int x,y;
      |        ^

• Subtask 1: 100 / 100