oj.uz

답안 #661475

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
661475 2022-11-25T22:08:36 Z yashsingh Job Scheduling (CEOI12_jobs) C++17
40 / 100
 688 ms 56916 KB 
#include <bits/stdc++.h>

using namespace std;

typedef int 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 93 ms 6476 KB Output is correct
2 Correct 104 ms 6324 KB Output is correct
3 Correct 89 ms 6336 KB Output is correct
4 Correct 91 ms 6340 KB Output is correct
5 Correct 94 ms 6328 KB Output is correct
6 Correct 98 ms 6324 KB Output is correct
7 Correct 91 ms 6324 KB Output is correct
8 Correct 89 ms 6296 KB Output is correct
9 Incorrect 63 ms 6564 KB Output isn't correct
10 Incorrect 72 ms 6476 KB Output isn't correct
11 Incorrect 76 ms 6324 KB Output isn't correct
12 Incorrect 156 ms 12484 KB Output isn't correct
13 Incorrect 220 ms 18636 KB Output isn't correct
14 Incorrect 345 ms 24944 KB Output isn't correct
15 Incorrect 354 ms 31096 KB Output isn't correct
16 Runtime error 473 ms 37256 KB Memory limit exceeded
17 Runtime error 538 ms 43384 KB Memory limit exceeded
18 Runtime error 601 ms 50508 KB Memory limit exceeded
19 Runtime error 688 ms 56916 KB Memory limit exceeded
20 Runtime error 529 ms 43448 KB Memory limit exceeded