Submission #529354

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
529354	2022-02-22T20:38:26 Z	nemethm	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	249 ms	13756 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	1604 KB	Output is correct
2	Correct	18 ms	1620 KB	Output is correct
3	Correct	16 ms	1632 KB	Output is correct
4	Correct	18 ms	1612 KB	Output is correct
5	Correct	18 ms	1608 KB	Output is correct
6	Correct	24 ms	1612 KB	Output is correct
7	Correct	16 ms	1620 KB	Output is correct
8	Correct	18 ms	1716 KB	Output is correct
9	Correct	30 ms	1872 KB	Output is correct
10	Correct	31 ms	1872 KB	Output is correct
11	Correct	25 ms	1612 KB	Output is correct
12	Correct	60 ms	3152 KB	Output is correct
13	Correct	72 ms	4580 KB	Output is correct
14	Correct	114 ms	6340 KB	Output is correct
15	Correct	121 ms	7552 KB	Output is correct
16	Correct	157 ms	9236 KB	Output is correct
17	Correct	186 ms	10780 KB	Output is correct
18	Correct	191 ms	12088 KB	Output is correct
19	Correct	249 ms	13756 KB	Output is correct
20	Correct	177 ms	10788 KB	Output is correct