oj.uz

Submission #532347

# Submission time Handle Problem Language Result Execution time Memory
532347 2022-03-02T18:06:24 Z Alex_tz307 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 390 ms 25412 KB 
#include <bits/stdc++.h>

using namespace std;

const int kN = 1e5;
const int kM = 1e6;
int n, d, m, dq[2 * kM];
pair<int, int> a[kM];
vector<int> sol[1 + kN];

/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

bool check(int k, bool ok = false) {
  int l = 0, r = -1;
  for (int i = 0; i < k; ++i) {
    dq[++r] = 0;
  }
  for (int i = 0; i < m; ++i) {
    int t = dq[l++];
    if (t > a[i].first + d) {
      return false;
    }
    dq[++r] = max(a[i].first + 1, t + 1);
    if (ok) {
      sol[dq[r] - 1].emplace_back(a[i].second + 1);
    }
  }
  return true;
}

void testCase() {
  cin >> n >> d >> m;
  for (int i = 0; i < m; ++i) {
    cin >> a[i].first;
    a[i].second = i;
  }
  sort(a, a + m);
  int l = 1, r = m;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (check(mid)) {
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  cout << l << '\n';
  check(l, true);
  for (int i = 1; i <= n; ++i) {
    for (int x : sol[i]) {
      cout << x << ' ';
    }
    cout << '0' << endl;
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5176 KB Output is correct
2 Correct 31 ms 5112 KB Output is correct
3 Correct 30 ms 5120 KB Output is correct
4 Correct 30 ms 5184 KB Output is correct
5 Correct 31 ms 5060 KB Output is correct
6 Correct 32 ms 5168 KB Output is correct
7 Correct 31 ms 5112 KB Output is correct
8 Correct 32 ms 5196 KB Output is correct
9 Correct 143 ms 5312 KB Output is correct
10 Correct 136 ms 5368 KB Output is correct
11 Correct 28 ms 5060 KB Output is correct
12 Correct 57 ms 7708 KB Output is correct
13 Correct 84 ms 10788 KB Output is correct
14 Correct 122 ms 13432 KB Output is correct
15 Correct 147 ms 14884 KB Output is correct
16 Correct 189 ms 17596 KB Output is correct
17 Correct 228 ms 22116 KB Output is correct
18 Correct 248 ms 23164 KB Output is correct
19 Correct 390 ms 25412 KB Output is correct
20 Correct 222 ms 22128 KB Output is correct