oj.uz

Submission #1083286

# Submission time Handle Problem Language Result Execution time Memory
1083286 2024-09-02T20:44:42 Z xiaowuc1 Job Scheduling (CEOI12_jobs) C++17
55 / 100
 223 ms 16976 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;
    for(int i = 0; i < n; i++) {
      int day = 1 + (i / mid);
      if(day > v[i][0] + k) {
        bad = true;
        break;
      }
    }
    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++) {
      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
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 2140 KB Output isn't correct
2 Incorrect 17 ms 2140 KB Output isn't correct
3 Incorrect 17 ms 2064 KB Output isn't correct
4 Incorrect 17 ms 2140 KB Output isn't correct
5 Incorrect 20 ms 2120 KB Output isn't correct
6 Incorrect 18 ms 2140 KB Output isn't correct
7 Incorrect 17 ms 1960 KB Output isn't correct
8 Incorrect 16 ms 2136 KB Output isn't correct
9 Correct 24 ms 2264 KB Output is correct
10 Correct 24 ms 2128 KB Output is correct
11 Correct 22 ms 2140 KB Output is correct
12 Correct 49 ms 4040 KB Output is correct
13 Correct 72 ms 5740 KB Output is correct
14 Correct 102 ms 8016 KB Output is correct
15 Incorrect 117 ms 9488 KB Output isn't correct
16 Correct 144 ms 11800 KB Output is correct
17 Correct 171 ms 13596 KB Output is correct
18 Correct 202 ms 14588 KB Output is correct
19 Correct 223 ms 16976 KB Output is correct
20 Correct 165 ms 13652 KB Output is correct