oj.uz

Submission #1088845

# Submission time Handle Problem Language Result Execution time Memory
1088845 2024-09-15T09:56:47 Z akamizane Job Scheduling (CEOI12_jobs) C++17
100 / 100
 263 ms 26460 KB 
#include<bits/stdc++.h>
 
using namespace std;

using ll = long long;
using pii = pair<int,int>;

#define el cout << '\n'
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T1, class T2>void chmax(T1 &a, T2 b){a = max(a, b);}
template <class T1, class T2>void chmin(T1 &a, T2 b){a = min(a, b);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e5 + 5;

const ll mod = 998244353;
int n, d, m;
vector<pii> x;

pair<bool, vector<vector<int>>> check (int mid){
  int cur = 0;
  vector<vector<int>> ans(n + 1);
  for (int day = 1; day <= n; day++){
    for (int j = 0; j < mid; j++){
      if (x[cur].fi > day) break;
      if (x[cur].fi + d < day) return {false, ans};
      ans[day].pb(x[cur].se);
      cur++;
      if (cur == m) return {true, ans};
    }
  }
  return {false, ans};
}

void solve(){
  
  cin >> n >> d >> m;
  x.resize(m);
  REP(i, m){
    cin >> x[i].fi;
    x[i].se = i + 1;
  }
  sort(all(x));
  vector<vector<int>> ans;
  int l = 0, r = m + 1;
  while(r - l > 1){
    int m = (l + r) / 2;
    auto [res1, res2] = check(m);
    if (res1) r = m, ans = res2;
    else l = m;
  }
    cout << r << '\n';
    FOR(i, 1, n){
      for (auto v : ans[i]) cout << v << " ";
      cout << 0 << '\n';
    }
}


int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tests = 1;
  //cin >> tests;
  for (int itest = 1; itest <= tests; itest++){
    //cerr << "- TEST " << itest << ": \n";
    solve();
    //el;
  }
  return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3212 KB Output is correct
2 Correct 24 ms 3216 KB Output is correct
3 Correct 23 ms 3088 KB Output is correct
4 Correct 28 ms 3088 KB Output is correct
5 Correct 29 ms 3232 KB Output is correct
6 Correct 28 ms 3216 KB Output is correct
7 Correct 23 ms 3216 KB Output is correct
8 Correct 22 ms 3216 KB Output is correct
9 Correct 54 ms 9832 KB Output is correct
10 Correct 57 ms 9932 KB Output is correct
11 Correct 25 ms 2740 KB Output is correct
12 Correct 55 ms 4908 KB Output is correct
13 Correct 72 ms 8740 KB Output is correct
14 Correct 122 ms 10872 KB Output is correct
15 Correct 125 ms 11168 KB Output is correct
16 Correct 177 ms 15932 KB Output is correct
17 Correct 234 ms 18820 KB Output is correct
18 Correct 215 ms 18464 KB Output is correct
19 Correct 263 ms 26460 KB Output is correct
20 Correct 205 ms 18852 KB Output is correct