Submission #1165021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165021		julia_08	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	790 ms	20456 KiB

jobs

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10;

vector<int> requests[MAXN], jobs[MAXN];

int n, d, m;

bool check(int x){

  priority_queue<pair<int, int>> q;

  for(int i=1; i<=n; i++){

    jobs[i].clear();

    for(auto j : requests[i]) q.push({-i, j});

    int cnt = 0;

    while(cnt < x && !q.empty()){
      if(-q.top().first < i - d) return false;

      jobs[i].push_back(q.top().second);
      q.pop();

      cnt ++;
    }

  }

  return true;
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> d >> m;

  for(int i=1; i<=m; i++){
    int d; cin >> d;
    requests[d].push_back(i);
  }

  int l = 1, r = m;

  while(l < r){
    int mid = l + (r - l) / 2;

    if(check(mid)) r = mid;
    else l = mid + 1;
  }

  check(r);

  cout << r << "\n";

  for(int i=1; i<=n; i++){
    for(auto j : jobs[i]) cout << j << " ";
    cout << 0 << "\n";
  }

  return 0;
}

• Subtask 1: 100 / 100