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

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;

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();
      |           ^~~~~

Subtask #1

90.0 / 100.0

#	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