oj.uz

답안 #531235

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
531235 2022-02-28T07:09:49 Z Stormersyle Job Scheduling (CEOI12_jobs) C++14
55 / 100
 353 ms 18196 KB 
#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

# 결과 실행 시간 메모리 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