Submission #296259

#	Time	Username	Problem	Language	Result	Execution time	Memory
296259		heon	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	250 ms	17016 KiB

jobs

#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
typedef vector <int> vi;
typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
const ll inf = 3e18 + 5;
int add(int a, int b) { return (a += b) < mod ? a : a - mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }
int sub(int a, int b) { return (a -= b) < 0 ? a + mod : a; }

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  #ifdef LOCAL
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif

  int n, d, m;
  cin >> n >> d >> m;
  vi v(m);
  vector <vi> ind(n + 1);
  for(int i = 0; i < m; i++) {
    cin >> v[i];
    ind[v[i]].push_back(i + 1);
  }
  sort(all(v));
  int lo = 0, hi = m;
  while(lo < hi) {
    int mid = (lo + hi + 1) / 2;
    int idx = 0;
    bool ok = 1;
    for(int day = 1; day <= n; day++) {
      int ava = mid;
      while(idx < m && ava > 0 && v[idx] <= day) {
        if(day - v[idx] > d)
          ok = 0;
        idx++;
        ava--;
      }
    }
    if(ok)
      hi = mid - 1;
    else
      lo = mid;
  }
  cout << lo + 1 << endl;
  int idx = 0;
  for(int day = 1; day <= n; day++) {
    int ava = lo + 1;
    while(idx < m && ava > 0 && v[idx] <= day) {
      cout << ind[v[idx]].back() << " ";
      ind[v[idx]].pop_back();
      idx++;
      ava--;
    }
    cout << 0 << "\n";
  }

}

• Subtask 1: 100 / 100