oj.uz

Submission #511474

# Submission time Handle Problem Language Result Execution time Memory
511474 2022-01-15T23:43:48 Z whaaaa Job Scheduling (CEOI12_jobs) C++11
100 / 100
 466 ms 16708 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1988 KB Output is correct
2 Correct 39 ms 1912 KB Output is correct
3 Correct 40 ms 1872 KB Output is correct
4 Correct 53 ms 1980 KB Output is correct
5 Correct 44 ms 1908 KB Output is correct
6 Correct 46 ms 1996 KB Output is correct
7 Correct 41 ms 1872 KB Output is correct
8 Correct 41 ms 1980 KB Output is correct
9 Correct 146 ms 4156 KB Output is correct
10 Correct 150 ms 4336 KB Output is correct
11 Correct 48 ms 1744 KB Output is correct
12 Correct 77 ms 3528 KB Output is correct
13 Correct 117 ms 5124 KB Output is correct
14 Correct 179 ms 6852 KB Output is correct
15 Correct 206 ms 8144 KB Output is correct
16 Correct 256 ms 9824 KB Output is correct
17 Correct 295 ms 11328 KB Output is correct
18 Correct 329 ms 12960 KB Output is correct
19 Correct 466 ms 16708 KB Output is correct
20 Correct 304 ms 11380 KB Output is correct