답안 #797067

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
797067 2023-07-29T05:45:58 Z arush_agu Job Scheduling (CEOI12_jobs) C++17
60 / 100
1000 ms 11512 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;

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();
      |           ^~~~~
# 결과 실행 시간 메모리 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