oj.uz

Submission #1020134

# Submission time Handle Problem Language Result Execution time Memory
1020134 2024-07-11T15:27:37 Z adrielcp Job Scheduling (CEOI12_jobs) C++17
100 / 100
 287 ms 22980 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lld double
#define int ll
#define usaco(fname) freopen(#fname ".in","r",stdin);freopen(#fname ".out","w",stdout);
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
// const ll INF = 1e18;
const int INF = 1e9;
const int mod = 1e9+7;
const lld PI = acos(-1.0);
int di[] = {1, -1, 0, 0, 1, 1, -1, -1};
int dj[] = {0, 0, 1, -1, 1, -1, 1, -1};
#define debug(x) cout << #x << ": " << x << endl;
#define add(a, b) a += b, a %= mod
#define mul(a, b) ((a % mod) * (b % mod)) % mod
#define all(x) x.begin(),x.end()

void solve() {
  int n,d,m;cin>>n>>d>>m;
  vector<pair<int, int>> a(m);
  for (int i = 0; i < m; i++) cin >> a[i].first, a[i].second = i;
  sort(all(a));
  
  // vector<pair<int, int>> s;
  int cnt = 0;
  function<bool(int, bool)> chk = [&](int k, bool ou) {
    int day = 1;
    for (int i = 0; i < m;) {
      int l = i;
      for (;i<min(l+k, m); i++) {
        if (a[i].first > day) break;
        if (ou) {
          cout << a[i].second+1 << " ";
        }
        if (a[i].first + d < day) return 0;  
      }
      if (ou) {
        cnt++;
        cout << 0 << endl;
      }
      day++;
    }
    return 1;
  };

  int l = 1, r = m;
  int ans = -1;
  while (l <= r) {
    int mid = (l+r)>>1;
    if (chk(mid,0)) {
      r = mid-1;
      ans = mid;
    } else l = mid+1;
  }
  cout << ans << endl;
  chk(ans, 1);
  for (int i = cnt; i < n; i++) cout << 0 << endl;
}

int32_t main() {
  ios_base::sync_with_stdio(0);cin.tie(0);
  int t=1;
  while(t--) solve();

  return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2904 KB Output is correct
2 Correct 23 ms 2724 KB Output is correct
3 Correct 23 ms 2904 KB Output is correct
4 Correct 23 ms 2908 KB Output is correct
5 Correct 23 ms 2916 KB Output is correct
6 Correct 23 ms 2908 KB Output is correct
7 Correct 23 ms 2904 KB Output is correct
8 Correct 22 ms 2880 KB Output is correct
9 Correct 114 ms 2896 KB Output is correct
10 Correct 118 ms 2908 KB Output is correct
11 Correct 21 ms 2908 KB Output is correct
12 Correct 40 ms 5212 KB Output is correct
13 Correct 61 ms 7704 KB Output is correct
14 Correct 93 ms 10580 KB Output is correct
15 Correct 103 ms 12884 KB Output is correct
16 Correct 145 ms 15700 KB Output is correct
17 Correct 163 ms 17808 KB Output is correct
18 Correct 176 ms 20304 KB Output is correct
19 Correct 287 ms 22980 KB Output is correct
20 Correct 181 ms 16016 KB Output is correct