Submission #296259

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
296259	2020-09-10T12:48:44 Z	heon	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	250 ms	17016 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	2164 KB	Output is correct
2	Correct	22 ms	2172 KB	Output is correct
3	Correct	22 ms	2172 KB	Output is correct
4	Correct	25 ms	2164 KB	Output is correct
5	Correct	22 ms	2164 KB	Output is correct
6	Correct	22 ms	2172 KB	Output is correct
7	Correct	22 ms	2172 KB	Output is correct
8	Correct	24 ms	2168 KB	Output is correct
9	Correct	33 ms	4472 KB	Output is correct
10	Correct	36 ms	4676 KB	Output is correct
11	Correct	27 ms	1920 KB	Output is correct
12	Correct	56 ms	3576 KB	Output is correct
13	Correct	83 ms	5752 KB	Output is correct
14	Correct	129 ms	7544 KB	Output is correct
15	Correct	138 ms	8700 KB	Output is correct
16	Correct	193 ms	11000 KB	Output is correct
17	Correct	228 ms	13304 KB	Output is correct
18	Correct	221 ms	13560 KB	Output is correct
19	Correct	250 ms	17016 KB	Output is correct
20	Correct	228 ms	13380 KB	Output is correct