Submission #797072

# Submission time Handle Problem Language Result Execution time Memory
797072 2023-07-29T05:56:52 Z arush_agu Job Scheduling (CEOI12_jobs) C++17
90 / 100
1000 ms 20212 KB
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#ifdef DEBUG
#include <time.h>
#endif

#define all(a) (a).begin(), (a).end()
#define rev(a) (a).rbegin(), (a).rend()
#define F first
#define S second
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x)                                                                 \
  {                                                                            \
    ++recur_depth;                                                             \
    auto x_ = x;                                                               \
    --recur_depth;                                                             \
    cerr << string(recur_depth, '\t') << "\e[91m" << __func__ << ":"           \
         << __LINE__ << "\t" << #x << " = " << x_ << "\e[39m" << endl;         \
  }
#else
#define dbg(x)
#endif

using namespace std;
using namespace __gnu_pbds;

typedef pair<int, int> ii;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> llll;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int>> vii;
typedef vector<vii> vvii;

typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pair<ll, ll>> vll;
typedef vector<vll> vvll;

typedef vector<bool> vb;

template <class type1>
using ordered_set = tree<type1, null_type, less<type1>, rb_tree_tag,
                         tree_order_statistics_node_update>;

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 MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 1e9;
const ld EPS = 1e-9;

const int MAXN = 1e5 + 10;
const int MAXM = 1e6 + 10;

int n, d, m;
ii as[MAXM];
vi on[MAXN];

void solve() {
  cin >> n >> d >> m;
  for (int i = 0; i < m; i++)
    cin >> as[i].first;

  for (int i = 0; i < m; i++)
    as[i].second = i;
  sort(as, as + m);

  auto check = [&](int no_mc) {
    priority_queue<ii, vii, greater<ii>> s;
    int m_idx = 0;
    for (int day = 1; day <= n; day++) {
      while (m_idx < m && as[m_idx].first == day)
        s.push(as[m_idx++]);

      for (int cnt = 0; cnt < no_mc; cnt++) {
        if (s.empty())
          break;

        auto [curr, _] = s.top();
        s.pop();

        if (day > curr + d)
          return false;
      }
    }

    return s.empty();
  };

  int l = 1, r = m - 1, ans = m;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (check(mid)) {
      r = mid - 1;
      ans = mid;
    } else
      l = mid + 1;
  }

  priority_queue<ii, vii, greater<ii>> s;
  int m_idx = 0;
  for (int day = 1; day <= n; day++) {
    while (m_idx < m && as[m_idx].first == day)
      s.push(as[m_idx++]);

    for (int cnt = 0; cnt < ans; cnt++) {
      if (s.empty())
        break;
      ii curr = s.top();
      s.pop();

      on[day].push_back(curr.second);
    }
  }

  cout << ans << "\n";
  for (int i = 1; i <= n; i++) {
    for (int &x : on[i])
      cout << x + 1 << " ";
    cout << "0\n";
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);

  clock_t start = clock();

  int test_cases = 1;
  // cin >> test_cases;

  while (test_cases--)
    solve();

#ifdef DEBUG
  cerr << fixed << setprecision(10)
       << "\nTime Taken: " << (double)(clock() - start) / CLOCKS_PER_SEC
       << "s\n";
#endif
  return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:168:11: warning: unused variable 'start' [-Wunused-variable]
  168 |   clock_t start = clock();
      |           ^~~~~
# Verdict Execution time Memory Grader output
1 Correct 136 ms 5852 KB Output is correct
2 Correct 138 ms 5824 KB Output is correct
3 Correct 136 ms 5848 KB Output is correct
4 Correct 144 ms 5972 KB Output is correct
5 Correct 136 ms 5748 KB Output is correct
6 Correct 136 ms 5820 KB Output is correct
7 Correct 137 ms 5804 KB Output is correct
8 Correct 137 ms 5832 KB Output is correct
9 Correct 117 ms 4800 KB Output is correct
10 Correct 123 ms 4896 KB Output is correct
11 Correct 70 ms 4468 KB Output is correct
12 Correct 249 ms 6668 KB Output is correct
13 Correct 290 ms 8976 KB Output is correct
14 Correct 362 ms 11500 KB Output is correct
15 Correct 422 ms 11948 KB Output is correct
16 Correct 340 ms 14140 KB Output is correct
17 Correct 531 ms 17992 KB Output is correct
18 Execution timed out 1016 ms 18588 KB Time limit exceeded
19 Execution timed out 1010 ms 20212 KB Time limit exceeded
20 Correct 558 ms 17992 KB Output is correct