oj.uz

답안 #661474

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
661474 2022-11-25T22:06:46 Z yashsingh Job Scheduling (CEOI12_jobs) C++17
40 / 100
 629 ms 65536 KB 
#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

# 결과 실행 시간 메모리 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