Submission #531235

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
531235	2022-02-28T07:09:49 Z	Stormersyle	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	353 ms	18196 KB

jobs

#include <iostream>
#include <bits/stdc++.h> 
#include <array>
#include <fstream>
#include <string>
#include <algorithm>
#include <cmath>
#include <sstream>  
using namespace std;
using ll=long long;

int N, D, M;
bool works(int k, int a[]){
  int t=1; //currently working on jobs w/ deadline t
  int b[N+1];
  for (int i=0; i<=N; i++) b[i]=a[i];
  for (int day=1; day<=N; day++){
    int j=k; //j=jobs left for today
    while (j>0){
      if (j<b[t]) b[t]-=j, j=0;
      else j-=b[t], b[t]=0, t++;
      if (t>N) return true;
    }
    if (t<=day) return false;
    // cout<<day<<" "<<t<<"\n";
  }
  return true;
}

int firstTrue(int lo, int hi, int a[]) {
	hi++;
	while (lo < hi) {
		int mid = lo + (hi - lo) / 2;
		if (works(mid, a)) {
			hi = mid;
		} else {
			lo = mid + 1;
		}
	}
	return lo;
}

int main() {
  cin>>N>>D>>M;
  int a[N+1]; //a[d]=# of jobs with deadline d
  for (int i=0; i<=N; i++) a[i]=0;
  vector<pair<int, int>> v; //{deadline, request id}
  for (int i=1; i<=M; i++){
    int S;
    cin>>S;
    a[S+D]++;
    v.push_back({S+D, i});
  }
  sort(v.begin(), v.end());
  // for (int i=1; i<=N; i++) cout<<a[i]<<" ";
  // cout<<works(2, a);
  int k=firstTrue(1, 1000000, a);
  cout<<k<<"\n";
  int t=0;
  for (int day=1; day<=N; day++){
    if (t<M){
      for (int i=0; i<k; i++){
        cout<<v[t].second<<" ";
        t++;
        if (t==M) break;
      }
    }
    cout<<"0\n";
  }
}

Subtask #1

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	35 ms	2132 KB	Output isn't correct
2	Incorrect	28 ms	2072 KB	Output isn't correct
3	Incorrect	29 ms	2060 KB	Output isn't correct
4	Incorrect	27 ms	2148 KB	Output isn't correct
5	Incorrect	30 ms	2152 KB	Output isn't correct
6	Incorrect	29 ms	2140 KB	Output isn't correct
7	Incorrect	32 ms	2192 KB	Output isn't correct
8	Incorrect	33 ms	2168 KB	Output isn't correct
9	Correct	37 ms	2920 KB	Output is correct
10	Correct	38 ms	2984 KB	Output is correct
11	Correct	37 ms	2092 KB	Output is correct
12	Correct	77 ms	3920 KB	Output is correct
13	Correct	133 ms	5836 KB	Output is correct
14	Correct	167 ms	8156 KB	Output is correct
15	Incorrect	186 ms	9556 KB	Output isn't correct
16	Correct	263 ms	12128 KB	Output is correct
17	Correct	293 ms	14184 KB	Output is correct
18	Correct	313 ms	15256 KB	Output is correct
19	Correct	353 ms	18196 KB	Output is correct
20	Correct	306 ms	14212 KB	Output is correct