Submission #797067

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
797067	2023-07-29T05:45:58 Z	arush_agu	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	1000 ms	11512 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) {
    multiset<int> s;
    int m_idx = 0;
    for (int day = 1; day <= n; day++) {
      while (m_idx < m && as[m_idx].first == day)
        s.insert(as[m_idx++].first);

      for (int cnt = 0; cnt < no_mc; cnt++)
        if (s.size()) {
          int curr = *s.begin();
          s.erase(s.begin());

          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);
  multiset<ii> s;
  int m_idx = 0;
  for (int day = 1; day <= n; day++) {
    while (m_idx < m && as[m_idx].first == day)
      s.insert(as[m_idx++]);

    for (int cnt = 0; cnt < ans; cnt++)
      if (s.size()) {
        ii curr = *s.begin();
        s.erase(s.begin());

        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	743 ms	6852 KB	Output is correct
2	Correct	742 ms	6836 KB	Output is correct
3	Correct	751 ms	6848 KB	Output is correct
4	Correct	753 ms	6836 KB	Output is correct
5	Correct	768 ms	6860 KB	Output is correct
6	Correct	780 ms	6860 KB	Output is correct
7	Correct	775 ms	6844 KB	Output is correct
8	Correct	803 ms	6956 KB	Output is correct
9	Execution timed out	1069 ms	1488 KB	Time limit exceeded
10	Execution timed out	1085 ms	1496 KB	Time limit exceeded
11	Correct	166 ms	2512 KB	Output is correct
12	Correct	401 ms	5708 KB	Output is correct
13	Correct	556 ms	7928 KB	Output is correct
14	Execution timed out	1071 ms	5232 KB	Time limit exceeded
15	Correct	922 ms	11512 KB	Output is correct
16	Execution timed out	1026 ms	7884 KB	Time limit exceeded
17	Execution timed out	1066 ms	9112 KB	Time limit exceeded
18	Execution timed out	1079 ms	9648 KB	Time limit exceeded
19	Execution timed out	1075 ms	10808 KB	Time limit exceeded
20	Execution timed out	1076 ms	9120 KB	Time limit exceeded