Submission #797071

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
797071	2023-07-29T05:55:39 Z	arush_agu	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	1000 ms	20192 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.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:169:11: warning: unused variable 'start' [-Wunused-variable]
  169 |   clock_t start = clock();
      |           ^~~~~

Subtask #1

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	301 ms	5764 KB	Output is correct
2	Correct	290 ms	5864 KB	Output is correct
3	Correct	291 ms	5764 KB	Output is correct
4	Correct	297 ms	5764 KB	Output is correct
5	Correct	300 ms	5760 KB	Output is correct
6	Correct	296 ms	5760 KB	Output is correct
7	Correct	290 ms	5808 KB	Output is correct
8	Correct	302 ms	5844 KB	Output is correct
9	Correct	266 ms	4828 KB	Output is correct
10	Correct	263 ms	4924 KB	Output is correct
11	Correct	70 ms	4488 KB	Output is correct
12	Correct	246 ms	6680 KB	Output is correct
13	Correct	294 ms	8984 KB	Output is correct
14	Correct	359 ms	11456 KB	Output is correct
15	Correct	426 ms	11960 KB	Output is correct
16	Correct	348 ms	14044 KB	Output is correct
17	Correct	560 ms	17968 KB	Output is correct
18	Execution timed out	1022 ms	18648 KB	Time limit exceeded
19	Execution timed out	1049 ms	20192 KB	Time limit exceeded
20	Correct	532 ms	17992 KB	Output is correct