oj.uz

Submission #797079

# Submission time Handle Problem Language Result Execution time Memory
797079 2023-07-29T06:08:19 Z arush_agu Job Scheduling (CEOI12_jobs) C++17
100 / 100
 250 ms 20164 KB 
#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) {
    deque<ii> s;
    int m_idx = 0;
    for (int day = 1; day <= n; day++) {
      while (m_idx < m && as[m_idx].first == day)
        s.push_back(as[m_idx++]);

      for (int cnt = 0; cnt < no_mc && s.size(); cnt++) {
        auto [curr, _] = s.front();
        s.pop_front();

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

  deque<ii> s;
  int m_idx = 0;
  for (int day = 1; day <= n; day++) {
    while (m_idx < m && as[m_idx].first == day)
      s.push_back(as[m_idx++]);

    for (int cnt = 0; cnt < ans && s.size(); cnt++) {
      ii curr = s.front();
      s.pop_front();

      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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5328 KB Output is correct
2 Correct 21 ms 5312 KB Output is correct
3 Correct 22 ms 5332 KB Output is correct
4 Correct 22 ms 5420 KB Output is correct
5 Correct 22 ms 5480 KB Output is correct
6 Correct 22 ms 5328 KB Output is correct
7 Correct 22 ms 5364 KB Output is correct
8 Correct 22 ms 5328 KB Output is correct
9 Correct 31 ms 4684 KB Output is correct
10 Correct 35 ms 4892 KB Output is correct
11 Correct 27 ms 4484 KB Output is correct
12 Correct 52 ms 6668 KB Output is correct
13 Correct 78 ms 8988 KB Output is correct
14 Correct 111 ms 11332 KB Output is correct
15 Correct 131 ms 12008 KB Output is correct
16 Correct 159 ms 14068 KB Output is correct
17 Correct 194 ms 17952 KB Output is correct
18 Correct 217 ms 18704 KB Output is correct
19 Correct 250 ms 20164 KB Output is correct
20 Correct 197 ms 18020 KB Output is correct