Submission #260093

#	Time	Username	Problem	Language	Result	Execution time	Memory
260093		tincamatei	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	349 ms	24184 KiB

jobs

#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 (stderr)

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 / 100