Submission #640060

#	Time	Username	Problem	Language	Result	Execution time	Memory
640060		Trisanu_Das	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	9 ms	536 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
 
int n, m, d; pair<int, int> tasks[1000005];
 
bool check(int mid){
  int pos = 1;
  for(int i = 1; i <= n; i++) for(int j = 1; j <= mid && pos <= m && tasks[pos].ff <= i; j++) if(i - tasks[pos++].ff > d) return 0;
  return (pos == m + 1);
}
 
int main(){
  cin >> n >> m >> d;
  for(int i = 0; i < m; i++) {cin >> tasks[i].ff; tasks[i].ss = i;}
  sort(tasks + 1, tasks + m + 1);
  int l = 1, r = m + 1;
  while(l < r){
    int mid = (l + r) / 2;
    if(check(mid)) r = mid; else l = mid + 1;
  }
  cout << r << '\n';
  int pos = 1;
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= r && pos <= m && tasks[pos].ff <= i; j++, pos++) cout << tasks[pos].ss << ' ';
	cout << 0 << '\n';
  }
}

• Subtask 1: 0 / 100