Submission #661474

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
661474	2022-11-25T22:06:46 Z	yashsingh	Job Scheduling (CEOI12_jobs)	C++17	40 / 100	629 ms	65536 KB

jobs

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n, d, m;

bool sort2(pair<ll,ll>a,pair<ll,ll>b) {
  return a.second < b.second;
}

bool val(ll machines, pair<ll,ll> a[]) {
  map<ll,ll> ma;
  ma.insert({0, machines});
  pair<ll,ll> val;
  for (ll i{0}; i < m; ++i) {
    auto search = ma.upper_bound(a[i].first+d);
    val = *prev(search);
    if (search == ma.begin()) {
      return 0;
    } else {
      prev(search)->second = val.second - 1;
      if (val.second == 1) {
        ma.erase(prev(search));
      }
      ++ma[max(val.first, a[i].first)+1];
    }
  }
  return 1;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> d >> m;
  pair<ll,ll> a[m];
  for (ll i{0}; i < m; ++i) {
    cin >> a[i].first;
    a[i].second = i;
  }
  sort(a,a+m);

  ll l{1}, r{m}, ans{-1};
  while (l <= r) {
    ll m{(l+r)/2};
    if (val(m, a)) {
      r = m - 1;
      ans = m;
    } else {
      l = m + 1;
    }
  }

  cout << ans << "\n";

  set<pair<ll,ll>> s;
  for (ll i{0}; i < m; ++i) {
    s.insert(a[i]);
  }
  for (ll i{0}; i < n; ++i) {
    ll mecuse{0};
    while (!s.empty() && mecuse < ans && s.begin()->first <= i + 1) {
      cout << s.begin()->second+1 << " ";
      s.erase(s.begin());
      ++mecuse;
    }
    cout << "0\n";
  }

  return 0;
}

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	94 ms	8664 KB	Output is correct
2	Correct	96 ms	8644 KB	Output is correct
3	Correct	89 ms	8660 KB	Output is correct
4	Correct	86 ms	8656 KB	Output is correct
5	Correct	88 ms	8656 KB	Output is correct
6	Correct	90 ms	8648 KB	Output is correct
7	Correct	90 ms	8652 KB	Output is correct
8	Correct	91 ms	8644 KB	Output is correct
9	Incorrect	64 ms	8904 KB	Output isn't correct
10	Incorrect	77 ms	8812 KB	Output isn't correct
11	Incorrect	71 ms	8696 KB	Output isn't correct
12	Incorrect	151 ms	17212 KB	Output isn't correct
13	Incorrect	230 ms	25728 KB	Output isn't correct
14	Runtime error	327 ms	34216 KB	Memory limit exceeded
15	Runtime error	367 ms	42772 KB	Memory limit exceeded
16	Runtime error	481 ms	51300 KB	Memory limit exceeded
17	Runtime error	577 ms	59900 KB	Memory limit exceeded
18	Runtime error	629 ms	65536 KB	Memory limit exceeded
19	Runtime error	604 ms	65536 KB	Execution killed with signal 9
20	Runtime error	560 ms	59820 KB	Memory limit exceeded