Submission #511474

#	Time	Username	Problem	Language	Result	Execution time	Memory
511474		whaaaa	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	466 ms	16708 KiB

jobs

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#define ll long long
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second
#define CHECKPOINT cout << "got here" << endl;
#define pb push_back
#define create_pfixsum(a,n,p) for(int i = 1; i < n; i++){p[i] = p[i-1] + a[i];}
using namespace std;
int n, d, m;
vector<vector<int>> ans;
vector<pi> a;
bool f(int l){
  int i = 0;
  int cur;
  for(int day = 1; day <= n; day++){
    cur = 0;
    while(i < m && a[i].f <= day && day <= a[i].f+d && cur < l){
      cur++;
      i++;
    }
  }
  if(i >= m){
    return true;
  }
  return false;
}

void printans(int l){
  ans.clear();
  ans.resize(n);
  int i = 0;
  int cur;
  for(int day = 1; day <= n; day++){
    cur = 0;
    while(i < m && a[i].f <= day && day <= a[i].f+d && cur < l){
      cout << a[i].s << ' ';
      cur++;
      i++;
    }
    cout << 0 << endl;
  }
}

int main() {
  cin >> n >> d >> m;
  a.resize(m);
  for(int i = 0; i < m ; i++){
    cin >> a[i].f;
    a[i].s = i+1;
  }
sort(all(a));
  int l = 1, r = m;
  while(l < r){
    int mid = l + (r-l) / 2;
    if(f(mid)){
      r = mid;
    } else {
      l = mid+1;
    }
  }
  cout << l << endl;
  printans(l);

}

• Subtask 1: 100 / 100