oj.uz

Submission #1083288

# Submission time Handle Problem Language Result Execution time Memory
1083288 2024-09-02T20:47:34 Z xiaowuc1 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 208 ms 17236 KB 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
typedef vector<int> vi;
#define f first
#define s second
#define derr if(1) cerr

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << flush;
// END NO SAD

template<class Fun>
class y_combinator_result {
  Fun fun_;
public:
  template<class T>
  explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

  template<class ...Args>
  decltype(auto) operator()(Args &&...args) {
    return fun_(std::ref(*this), std::forward<Args>(args)...);
  }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
  return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

template<class T>
bool updmin(T& a, T b) {
  if(b < a) {
    a = b;
    return true;
  }
  return false;
}
template<class T>
bool updmax(T& a, T b) {
  if(b > a) {
    a = b;
    return true;
  }
  return false;
}
typedef int64_t ll;
typedef long double ld;

void solve() {
  int nday, k, n;
  cin >> nday >> k >> n;
  vector<array<int, 2>> v;
  v.reserve(n);
  for(int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    v.pb({x, i});
  }
  sort(all(v));
  int lhs = 1;
  int rhs = n;
  while(lhs < rhs) {
    int mid = (lhs+rhs)/2;
    bool bad = false;
    int cday = 1;
    int chave = mid;
    for(int i = 0; i < n; i++) {
      if(v[i][0] > cday) {
        cday = v[i][0];
        chave = mid;
      }
      if(cday > v[i][0] + k) {
        bad = true;
        break;
      }
      if(--chave == 0) {
        cday++;
        chave = mid;
      }
    }
    if(bad) lhs = mid+1;
    else rhs = mid;
  }
  cout << lhs << "\n";
  int idx = 0;
  for(int i = 0; i < nday; i++) {
    for(int j = 0; idx < n && j < lhs; j++) {
      if(v[idx][0] > i+1) break;
      cout << v[idx++][1] << " ";
    }
    cout << "0\n";
  }
  assert(idx == n);
}

// what would chika do
// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases
// are you doing geometry in floating points
// are you not using modint when you should

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2064 KB Output is correct
2 Correct 16 ms 2004 KB Output is correct
3 Correct 18 ms 2120 KB Output is correct
4 Correct 19 ms 2140 KB Output is correct
5 Correct 19 ms 2028 KB Output is correct
6 Correct 18 ms 2036 KB Output is correct
7 Correct 18 ms 2024 KB Output is correct
8 Correct 18 ms 2056 KB Output is correct
9 Correct 24 ms 2264 KB Output is correct
10 Correct 23 ms 2140 KB Output is correct
11 Correct 23 ms 2204 KB Output is correct
12 Correct 59 ms 4056 KB Output is correct
13 Correct 74 ms 5856 KB Output is correct
14 Correct 97 ms 8020 KB Output is correct
15 Correct 121 ms 9548 KB Output is correct
16 Correct 147 ms 12112 KB Output is correct
17 Correct 166 ms 13884 KB Output is correct
18 Correct 189 ms 15128 KB Output is correct
19 Correct 208 ms 17236 KB Output is correct
20 Correct 169 ms 13872 KB Output is correct