oj.uz

Submission #157727

# Submission time Handle Problem Language Result Execution time Memory
157727 2019-10-12T18:47:07 Z a_player Job Scheduling (CEOI12_jobs) C++14
46 / 100
 930 ms 23964 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;
    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
46.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 86 ms 4892 KB Partially correct
2 Partially correct 86 ms 4856 KB Partially correct
3 Partially correct 86 ms 4804 KB Partially correct
4 Partially correct 86 ms 4860 KB Partially correct
5 Partially correct 90 ms 4804 KB Partially correct
6 Partially correct 89 ms 4856 KB Partially correct
7 Partially correct 86 ms 4784 KB Partially correct
8 Partially correct 86 ms 4856 KB Partially correct
9 Partially correct 342 ms 7416 KB Partially correct
10 Partially correct 340 ms 7464 KB Partially correct
11 Partially correct 65 ms 3576 KB Partially correct
12 Correct 131 ms 4216 KB Output is correct
13 Partially correct 178 ms 5216 KB Partially correct
14 Correct 290 ms 5756 KB Output is correct
15 Partially correct 320 ms 9208 KB Partially correct
16 Partially correct 474 ms 12672 KB Partially correct
17 Partially correct 486 ms 8316 KB Partially correct
18 Partially correct 600 ms 19648 KB Partially correct
19 Partially correct 930 ms 23964 KB Partially correct
20 Partially correct 483 ms 8184 KB Partially correct