Submission #529348

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
529348	2022-02-22T20:18:35 Z	nemethm	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	214 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(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 true;
}

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;
  }
  for(auto i : compressed){
    //cerr << i.first << " " << i.second << endl;
  }
  cerr << endl;
  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){
    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 'int main()':
jobs.cpp:59:12: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   59 |   for(auto i : compressed){
      |            ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	1612 KB	Output is correct
2	Correct	15 ms	1612 KB	Output is correct
3	Correct	17 ms	1620 KB	Output is correct
4	Correct	16 ms	1612 KB	Output is correct
5	Correct	16 ms	1612 KB	Output is correct
6	Correct	18 ms	1704 KB	Output is correct
7	Correct	17 ms	1720 KB	Output is correct
8	Correct	18 ms	1644 KB	Output is correct
9	Correct	30 ms	1856 KB	Output is correct
10	Correct	29 ms	1792 KB	Output is correct
11	Correct	23 ms	1708 KB	Output is correct
12	Correct	45 ms	3172 KB	Output is correct
13	Correct	72 ms	4676 KB	Output is correct
14	Correct	103 ms	6340 KB	Output is correct
15	Correct	114 ms	7544 KB	Output is correct
16	Correct	153 ms	9412 KB	Output is correct
17	Correct	171 ms	10780 KB	Output is correct
18	Correct	186 ms	12068 KB	Output is correct
19	Correct	214 ms	13756 KB	Output is correct
20	Correct	171 ms	10800 KB	Output is correct