Submission #1042671

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1042671	2024-08-03T09:27:00 Z	joelgun14	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	178 ms	30264 KB

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

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	4052 KB	Output is correct
2	Correct	20 ms	4040 KB	Output is correct
3	Correct	21 ms	4048 KB	Output is correct
4	Correct	19 ms	4048 KB	Output is correct
5	Correct	21 ms	4052 KB	Output is correct
6	Correct	24 ms	4048 KB	Output is correct
7	Correct	19 ms	4052 KB	Output is correct
8	Correct	20 ms	4048 KB	Output is correct
9	Correct	37 ms	10276 KB	Output is correct
10	Correct	32 ms	10320 KB	Output is correct
11	Correct	20 ms	2904 KB	Output is correct
12	Correct	45 ms	5632 KB	Output is correct
13	Correct	61 ms	9552 KB	Output is correct
14	Correct	91 ms	12920 KB	Output is correct
15	Correct	85 ms	13464 KB	Output is correct
16	Correct	123 ms	17272 KB	Output is correct
17	Correct	151 ms	22308 KB	Output is correct
18	Correct	154 ms	22212 KB	Output is correct
19	Correct	178 ms	30264 KB	Output is correct
20	Correct	155 ms	22392 KB	Output is correct