oj.uz

Submission #260093

# Submission time Handle Problem Language Result Execution time Memory
260093 2020-08-09T09:31:57 Z tincamatei Job Scheduling (CEOI12_jobs) C++14
100 / 100
 349 ms 24184 KB 
#include <bits/stdc++.h>

const int MAX_M = 1000000;
const int MAX_N = 100000;

struct Request {
  int id, submit, assigned;
}requests[MAX_M];

bool cmp(Request a, Request b) {
  return a.submit < b.submit;
}

bool check(int N, int D, int M, int K) {
  int lastjob = 0;
  for(int i = 1; i <= N; ++i) {
    int used = 0;
    while(lastjob < M && requests[lastjob].submit <= i && used < K) {
      if(requests[lastjob].submit + D < i)
        return false;
      requests[lastjob].assigned = i;
      ++lastjob;
      ++used;
    }
  }
  return true;
}

std::vector<int> jobs[1+MAX_N];

int main() {
	int N, D, M;

  scanf("%d%d%d", &N, &D, &M);
  for(int i = 0; i < M; ++i) {
    scanf("%d", &requests[i].submit);
    requests[i].id = i + 1;
  }

  std::sort(requests, requests + M, cmp);
  
  int st = 0, dr = M + 1;
  while(dr - st > 1) {
    int mid = (st + dr) / 2;
    if(check(N, D, M, mid))
      dr = mid;
    else
      st = mid;
  }

  printf("%d\n", dr);
  for(int i = 0; i < M; ++i)
    jobs[requests[i].assigned].push_back(requests[i].id);

  for(int i = 1; i <= N; ++i) {
    for(auto it: jobs[i])
      printf("%d ", it);
    printf("0\n");
  }

  return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &N, &D, &M);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &requests[i].submit);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5364 KB Output is correct
2 Correct 31 ms 5244 KB Output is correct
3 Correct 31 ms 5236 KB Output is correct
4 Correct 31 ms 5236 KB Output is correct
5 Correct 31 ms 5236 KB Output is correct
6 Correct 33 ms 5236 KB Output is correct
7 Correct 45 ms 5236 KB Output is correct
8 Correct 31 ms 5236 KB Output is correct
9 Correct 58 ms 5368 KB Output is correct
10 Correct 40 ms 5624 KB Output is correct
11 Correct 43 ms 5368 KB Output is correct
12 Correct 76 ms 7672 KB Output is correct
13 Correct 120 ms 10616 KB Output is correct
14 Correct 164 ms 13224 KB Output is correct
15 Correct 188 ms 14328 KB Output is correct
16 Correct 243 ms 17016 KB Output is correct
17 Correct 281 ms 21240 KB Output is correct
18 Correct 295 ms 22136 KB Output is correct
19 Correct 349 ms 24184 KB Output is correct
20 Correct 281 ms 21240 KB Output is correct