Submission #797069

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
797069	2023-07-29T05:51:23 Z	arush_agu	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	1000 ms	9680 KB

jobs

#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;

void solve() {
  int n, d, m;
  cin >> n >> d >> m;
  vii as(m);
  for (auto &[x, _] : as)
    cin >> x;

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

  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.size()) {
          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;
  }

  vvi on(n + 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.size()) {
        ii curr = s.top();
        s.pop();

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

        assert(day <= curr.first + d);
      }
  }

  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:163:11: warning: unused variable 'start' [-Wunused-variable]
  163 |   clock_t start = clock();
      |           ^~~~~

Subtask #1

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	451 ms	3668 KB	Output is correct
2	Correct	467 ms	3720 KB	Output is correct
3	Correct	455 ms	3668 KB	Output is correct
4	Correct	454 ms	3660 KB	Output is correct
5	Correct	465 ms	3724 KB	Output is correct
6	Correct	457 ms	3656 KB	Output is correct
7	Correct	464 ms	3664 KB	Output is correct
8	Correct	473 ms	3712 KB	Output is correct
9	Execution timed out	1084 ms	1108 KB	Time limit exceeded
10	Execution timed out	1084 ms	1120 KB	Time limit exceeded
11	Correct	98 ms	2128 KB	Output is correct
12	Correct	301 ms	4332 KB	Output is correct
13	Correct	382 ms	6692 KB	Output is correct
14	Execution timed out	1078 ms	3448 KB	Time limit exceeded
15	Correct	570 ms	9680 KB	Output is correct
16	Execution timed out	1082 ms	5020 KB	Time limit exceeded
17	Execution timed out	1085 ms	5796 KB	Time limit exceeded
18	Execution timed out	1087 ms	6484 KB	Time limit exceeded
19	Execution timed out	1085 ms	7352 KB	Time limit exceeded
20	Execution timed out	1088 ms	5792 KB	Time limit exceeded