oj.uz

Submission #157726

# Submission time Handle Problem Language Result Execution time Memory
157726 2019-10-12T18:46:34 Z a_player Job Scheduling (CEOI12_jobs) C++14
61 / 100
 926 ms 23160 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;
  int k=M/N+1;
    for(int i=0;i<M;i++){
      if(i%k==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:44: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
61.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 89 ms 4728 KB Partially correct
2 Partially correct 86 ms 4856 KB Partially correct
3 Partially correct 86 ms 4728 KB Partially correct
4 Partially correct 86 ms 4856 KB Partially correct
5 Partially correct 86 ms 4768 KB Partially correct
6 Partially correct 87 ms 4832 KB Partially correct
7 Partially correct 90 ms 4856 KB Partially correct
8 Partially correct 90 ms 4856 KB Partially correct
9 Partially correct 352 ms 5936 KB Partially correct
10 Partially correct 347 ms 5804 KB Partially correct
11 Correct 62 ms 3560 KB Output is correct
12 Correct 120 ms 4312 KB Output is correct
13 Correct 175 ms 4984 KB Output is correct
14 Correct 286 ms 5880 KB Output is correct
15 Partially correct 308 ms 8816 KB Partially correct
16 Correct 412 ms 7416 KB Output is correct
17 Correct 484 ms 8168 KB Output is correct
18 Partially correct 597 ms 19568 KB Partially correct
19 Partially correct 926 ms 23160 KB Partially correct
20 Correct 482 ms 8172 KB Output is correct