Submission #439490

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
439490	2021-06-30T06:01:02 Z	sksusha8853	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	474 ms	25804 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	3136 KB	Output is correct
2	Correct	38 ms	3112 KB	Output is correct
3	Correct	38 ms	3072 KB	Output is correct
4	Correct	37 ms	3136 KB	Output is correct
5	Correct	38 ms	3072 KB	Output is correct
6	Correct	37 ms	3096 KB	Output is correct
7	Correct	38 ms	3164 KB	Output is correct
8	Correct	43 ms	3140 KB	Output is correct
9	Correct	71 ms	5456 KB	Output is correct
10	Correct	54 ms	5520 KB	Output is correct
11	Correct	47 ms	2884 KB	Output is correct
12	Correct	102 ms	5732 KB	Output is correct
13	Correct	155 ms	8900 KB	Output is correct
14	Correct	245 ms	12412 KB	Output is correct
15	Correct	238 ms	13476 KB	Output is correct
16	Correct	321 ms	16836 KB	Output is correct
17	Correct	379 ms	21092 KB	Output is correct
18	Correct	404 ms	21852 KB	Output is correct
19	Correct	474 ms	25804 KB	Output is correct
20	Correct	371 ms	21148 KB	Output is correct