Submission #529340

#	Time	Username	Problem	Language	Result	Execution time	Memory
529340		nemethm	Job Scheduling (CEOI12_jobs)	C++17	25 / 100	227 ms	13764 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;

bool possible(vector<pair<int,int>>& v, int d, int m){
  priority_queue<pair<int,int>> q;
  int day = 1;
  for(auto i : v){
    q.push({-i.first, i.second});
    int sum = 0;
    while(!q.empty() && sum < m){
      auto p = q.top(); q.pop();
      p.first = -p.first;
      if(day > p.first + d){    //!!
        return false;
      }
      if(p.second > m - sum){
        q.push({-p.first, p.second - (m - sum)});
      }
      sum += p.second;
    }
    ++day;
  }
  return true;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, 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) / 2;
    if(possible(compressed, d, middle)){
      r = middle;
    }
    else{
      l = middle + 1;
    }
  }
  cout << l << endl;
  int i = 0;
  int day = 1;
  while(i < m){
    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;
  }
} 

• Subtask 1: 25 / 100