oj.uz

Submission #1083284

# Submission time Handle Problem Language Result Execution time Memory
1083284 2024-09-02T20:42:28 Z xiaowuc1 Job Scheduling (CEOI12_jobs) C++17
55 / 100
 250 ms 17216 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";
  }
}

// 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 18 ms 2132 KB Output isn't correct
2 Incorrect 16 ms 2060 KB Output isn't correct
3 Incorrect 18 ms 1972 KB Output isn't correct
4 Incorrect 16 ms 2140 KB Output isn't correct
5 Incorrect 17 ms 1904 KB Output isn't correct
6 Incorrect 18 ms 2060 KB Output isn't correct
7 Incorrect 19 ms 2060 KB Output isn't correct
8 Incorrect 16 ms 1980 KB Output isn't correct
9 Correct 28 ms 2052 KB Output is correct
10 Correct 29 ms 2096 KB Output is correct
11 Correct 24 ms 2144 KB Output is correct
12 Correct 52 ms 3944 KB Output is correct
13 Correct 74 ms 5720 KB Output is correct
14 Correct 97 ms 8140 KB Output is correct
15 Incorrect 118 ms 9624 KB Output isn't correct
16 Correct 147 ms 12120 KB Output is correct
17 Correct 173 ms 14064 KB Output is correct
18 Correct 205 ms 15124 KB Output is correct
19 Correct 250 ms 17216 KB Output is correct
20 Correct 173 ms 13900 KB Output is correct