Submission #797076

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
797076	2023-07-29T06:03:20 Z	arush_agu	Job Scheduling (CEOI12_jobs)	C++17	35 / 100	301 ms	30072 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 && s.size(); cnt++) {
        auto [curr, _] = s.top();
        s.pop();

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

    return s.empty();
  };

  int l = 1, r = (m + n - 1) / n, ans = r + 1;
  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 && s.size(); cnt++) {
      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:163:11: warning: unused variable 'start' [-Wunused-variable]
  163 |   clock_t start = clock();
      |           ^~~~~

Subtask #1

35.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	24 ms	5916 KB	Output isn't correct
2	Incorrect	24 ms	5784 KB	Output isn't correct
3	Incorrect	24 ms	5792 KB	Output isn't correct
4	Incorrect	25 ms	5840 KB	Output isn't correct
5	Incorrect	27 ms	5808 KB	Output isn't correct
6	Incorrect	25 ms	5888 KB	Output isn't correct
7	Incorrect	25 ms	5812 KB	Output isn't correct
8	Incorrect	26 ms	5856 KB	Output isn't correct
9	Incorrect	34 ms	6612 KB	Output isn't correct
10	Incorrect	43 ms	6520 KB	Output isn't correct
11	Correct	37 ms	4456 KB	Output is correct
12	Correct	159 ms	6700 KB	Output is correct
13	Correct	157 ms	9032 KB	Output is correct
14	Correct	301 ms	11420 KB	Output is correct
15	Incorrect	168 ms	11928 KB	Output isn't correct
16	Correct	151 ms	14120 KB	Output is correct
17	Correct	296 ms	18036 KB	Output is correct
18	Incorrect	258 ms	25192 KB	Output isn't correct
19	Incorrect	297 ms	30072 KB	Output isn't correct
20	Correct	291 ms	17988 KB	Output is correct