Submission #529354

#	Time	Username	Problem	Language	Result	Execution time	Memory
529354		nemethm	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	249 ms	13756 KiB

jobs

#include <iostream>
#include <vector>
#include <deque>
#include <set>
#include <queue>
#include <string>
#include <limits>
#include <map>
#include <algorithm>
#include <stack>

using namespace std;
using ll = long long int;
const ll mod = 1e9 + 7;
int n;
bool possible(vector<pair<int,int>>& v, int d, int m){
  set<pair<int,int>> q;
  int day = 1;
  int index = 0;
  while(day <= n){
    if(index < v.size() && v[index].first == day){
      q.insert({v[index].first, v[index].second});
      ++index;
    }
    int sum = 0;
    while(!q.empty() && sum < m){
      auto p = *q.begin(); q.erase(q.begin());
      if(day > p.first + d){    //!!
        return false;
      }
      if(p.second > m - sum){
        q.insert({p.first, p.second - (m - sum)});
      }
      sum += p.second;
    }
    ++day;
  }
  return q.empty();
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int d, m;
  cin >> n >>d >> m;
  vector<pair<int,int>> v(m);
  for(int i = 0; i < m; ++i){
    cin >> v[i].first;
    v[i].second = i + 1;
  }
  sort(begin(v), end(v));
  vector<pair<int,int>> compressed;
  for(int i = 0; i < m; ++i){
    if(compressed.empty() || compressed.back().first != v[i].first){
      compressed.push_back(make_pair(v[i].first, 0));
    }
    ++compressed.back().second;
  }
  int l = 1, r = m;
  while(l < r){
    int middle = l + (r - l) / 2;
    if(possible(compressed, d, middle)){
      r = middle;
    }
    else{
      l = middle + 1;
    }
  }
  cout << l << endl;
  int i = 0;
  int day = 1;
  while(i < m){
    if(v[i].first <= day){
      int ctr = 1;
      cout << v[i].second << " ";
      ++i;
      while(i < m && ctr < l && v[i].first <= day){
        cout << v[i].second << " ";
        ++ctr;
        ++i;
      }
    }
    ++day;
    cout << 0 << "\n";
  }
  while(day <= n){
    cout << 0 << "\n";
    ++day;
  }
} 

Compilation message (stderr)

jobs.cpp: In function 'bool possible(std::vector<std::pair<int, int> >&, int, int)':
jobs.cpp:21:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     if(index < v.size() && v[index].first == day){
      |        ~~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100