Submission #1042671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042671		joelgun14	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	178 ms	30264 KiB

jobs

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl "\n"
#define ll long long
#define mp make_pair
#define ins insert
#define lb lower_bound
#define pb push_back
#define ub upper_bound
#define lll __int128
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int main() {
  ios_base::sync_with_stdio(0); cin.tie(NULL);
  int n, d, m;
  cin >> n >> d >> m;
  int a[m + 1];
  for(int i = 1; i <= m; ++i)
    cin >> a[i];
  vector<int> cnt[n + 1];
  memset(cnt, 0, sizeof(cnt));
  for(int i = 1; i <= m; ++i)
    cnt[a[i]].pb(i);
  int l = 0, r = 1e6, ans = -1;
  vector<int> proc[n + 1];
  while(l <= r) {
    int mid = (l + r) / 2;
    queue<pair<int, int>> pend;
    bool valid = 1;
    vector<int> cur[n + 1];
    for(int i = 1; i <= n; ++i) {
      for(auto x : cnt[i])
        pend.push(mp(x, i));
      int sz = pend.size();
      for(int j = 0; j < min(sz, mid); ++j)
        valid &= pend.front().se >= i - d, cur[i].pb(pend.front().fi), pend.pop();
    }
    if(pend.empty() && valid) {
      for(int i = 1; i <= n; ++i)
        proc[i] = cur[i];
      r = mid - 1, ans = mid; 
    }
    else
      l = mid + 1;
  } 
  cout << ans << endl;
  for(int i = 1; i <= n; ++i) {
    for(auto j : proc[i])
      cout << j << " ";
    cout << 0 << endl;
  }
  return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:26:29: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'class std::vector<int>' with no trivial copy-assignment; use assignment or value-initialization instead [-Wclass-memaccess]
   26 |   memset(cnt, 0, sizeof(cnt));
      |                             ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from jobs.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:389:11: note: 'class std::vector<int>' declared here
  389 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~

• Subtask 1: 100 / 100