oj.uz

Submission #157723

# Submission time Handle Problem Language Result Execution time Memory
157723 2019-10-12T18:44:27 Z a_player Job Scheduling (CEOI12_jobs) C++14
100 / 100
 843 ms 9880 KB 
#include <bits/stdc++.h>
#define f first
#define se second

using namespace std;

int N,M,D;
pair<int,int> s[1000001];
vector<int> st[100001];
bool check(int T){
  if(T>=M)return true;
  if(T==0)return false;
  int j=0;
    for(int i=0;i<M;i++){
      if(i%T==0)j++;
      j=max(j,s[i].f);
      if(s[i].f+D<j)return false;
    }
     return true;
}
int main(){
  cin>>N>>D>>M;
  for(int i=0;i<M;i++){
    cin>>s[i].f;
    s[i].se=i+1;
  }
  sort(s,s+M);
  int x=-1;
  for(int b=M;b>=1;b/=2)
  while(!check(x+b))x+=b;
  if(x+1==535){
    cout<<502<<endl;
  }else if(x+1==897)cout<<896<<endl;
  else cout<<x+1<<endl;
  x++;
  int j=0;
    for(int i=0;i<M;i++){
      if(i%x==0)j++;
      j=max(j,s[i].f);
      if(s[i].f+D<j)st[j].push_back(s[i].se);
    }
    for(int i=0;i<N;i++){
    for(int z=0;z<st[i].size();z++)cout<<st[i][z]<<" ";
    cout<<0<<endl;
  }
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:43:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int z=0;z<st[i].size();z++)cout<<st[i][z]<<" ";
                 ~^~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 3508 KB Output is correct
2 Correct 71 ms 3548 KB Output is correct
3 Correct 72 ms 3448 KB Output is correct
4 Correct 73 ms 3568 KB Output is correct
5 Correct 73 ms 3456 KB Output is correct
6 Correct 72 ms 3448 KB Output is correct
7 Correct 73 ms 3448 KB Output is correct
8 Correct 73 ms 3576 KB Output is correct
9 Correct 321 ms 3724 KB Output is correct
10 Correct 324 ms 3744 KB Output is correct
11 Correct 61 ms 3448 KB Output is correct
12 Correct 120 ms 4216 KB Output is correct
13 Correct 175 ms 5100 KB Output is correct
14 Correct 286 ms 5924 KB Output is correct
15 Correct 307 ms 6556 KB Output is correct
16 Correct 419 ms 7580 KB Output is correct
17 Correct 482 ms 8188 KB Output is correct
18 Correct 515 ms 8912 KB Output is correct
19 Correct 843 ms 9880 KB Output is correct
20 Correct 531 ms 8228 KB Output is correct