Submission #297211

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
297211	2020-09-11T11:32:09 Z	EJOI2019Andrew	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	255 ms	20600 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	23 ms	2428 KB	Output is correct
2	Correct	25 ms	2676 KB	Output is correct
3	Correct	22 ms	2428 KB	Output is correct
4	Correct	24 ms	2428 KB	Output is correct
5	Correct	22 ms	2428 KB	Output is correct
6	Correct	22 ms	2428 KB	Output is correct
7	Correct	22 ms	2556 KB	Output is correct
8	Correct	23 ms	2428 KB	Output is correct
9	Correct	34 ms	4728 KB	Output is correct
10	Correct	38 ms	4864 KB	Output is correct
11	Correct	28 ms	2432 KB	Output is correct
12	Correct	55 ms	4216 KB	Output is correct
13	Correct	83 ms	6904 KB	Output is correct
14	Correct	136 ms	9464 KB	Output is correct
15	Correct	138 ms	10616 KB	Output is correct
16	Correct	197 ms	13944 KB	Output is correct
17	Correct	237 ms	16632 KB	Output is correct
18	Correct	222 ms	16632 KB	Output is correct
19	Correct	255 ms	20600 KB	Output is correct
20	Correct	237 ms	16760 KB	Output is correct