oj.uz

Submission #999557

# Submission time Handle Problem Language Result Execution time Memory
999557 2024-06-15T19:29:46 Z m_bezrutchka Job Scheduling (CEOI12_jobs) C++14
55 / 100
 140 ms 5904 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10;

int n, d, m;
pair<int, int> requests[10*MAXN];
vector <int> resp[MAXN];

bool possible(int k) {
  if (k <= 0) return false;
  if (k >= m) return true;
  int pos = 0;
  for (int day = 1; day <= n; day++) {
    resp[day].clear();
    for (int j = 0; j < k; j++) {
      if (pos >= m) break;
      int day_pos = requests[pos].first;
      int idx_pos = requests[pos].second;
      if (day_pos > day) break;
      if (day_pos + d < day) return false;
      resp[day].push_back(idx_pos);
      pos++;
    }
  }
  return (pos >= m);
}

int b_search() {
  int l = 0, r = m;
  while (l < r) {
    int mid = (l + r) / 2;
    if (possible(mid)) r = mid;
    else l = mid + 1;
  }
  return r;
}

int main() {
  cin >> n >> d >> m;
  if (m > (int)1e5) return 0;
  int x;
  for (int i = 0; i < m; i++) {
    cin >> x;
    requests[i] = {x, i + 1};
  }
  sort(requests, requests + m);
  int ans = b_search();
  cout << ans << endl;
  
  possible(ans);
  for (int i = 1; i <= n; i++) {
    for (int x : resp[i]) cout << x << " ";
    cout << 0 << endl;
  }
  return 0;
}

Subtask #1
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5724 KB Output is correct
2 Correct 29 ms 5720 KB Output is correct
3 Correct 29 ms 5772 KB Output is correct
4 Correct 30 ms 5756 KB Output is correct
5 Correct 30 ms 5720 KB Output is correct
6 Correct 32 ms 5788 KB Output is correct
7 Correct 30 ms 5724 KB Output is correct
8 Correct 30 ms 5724 KB Output is correct
9 Correct 140 ms 5860 KB Output is correct
10 Correct 125 ms 5904 KB Output is correct
11 Correct 35 ms 5716 KB Output is correct
12 Incorrect 1 ms 4700 KB Unexpected end of file - int32 expected
13 Incorrect 1 ms 4700 KB Unexpected end of file - int32 expected
14 Incorrect 1 ms 4700 KB Unexpected end of file - int32 expected
15 Incorrect 1 ms 4700 KB Unexpected end of file - int32 expected
16 Incorrect 1 ms 4696 KB Unexpected end of file - int32 expected
17 Incorrect 1 ms 4700 KB Unexpected end of file - int32 expected
18 Incorrect 1 ms 4696 KB Unexpected end of file - int32 expected
19 Incorrect 1 ms 4696 KB Unexpected end of file - int32 expected
20 Incorrect 1 ms 4700 KB Unexpected end of file - int32 expected