oj.uz

Submission #157779

# Submission time Handle Problem Language Result Execution time Memory
157779 2019-10-12T21:51:50 Z InfiniteJest Job Scheduling (CEOI12_jobs) C++14
55 / 100
 831 ms 13860 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;

ifstream in("input.txt");
ofstream out("output.txt");

typedef long long ll;

int n,dk,m;
pair<int,int> v[1000001];

bool funz(int k){
  int p=1;
  for(int i=0;i<m;i+=k){
    for(int y=i;y<i+k&&y<m;y++){
      if(p>v[y].fi+dk)return 0;
    }
    p++;
  }
  return 1;
}

int main(){
  cin>>n>>dk>>m;
  for(int i=0;i<m;i++){
    cin>>v[i].fi;
    v[i].se=i;
  }
  sort(v,v+m);

  int s=1;
  int d=m;
  int minn=1e9;

  while(s<=d){
    int k=(s+d)/2;
    if(funz(k)){
      minn=min(minn,k);
      d=k-1;
    }
    else{
      s=k+1;
    }
  }
  cout<<minn<<endl;
  for(int i=0;i<m;i+=minn){
    for(int y=i;y<i+minn&&y<m;y++){
      cout<<v[y].se+1<<" ";
    }
    cout<<0<<endl;
  }
  for(int i=m/minn+min(1,m%minn);i<n;i++){
    cout<<0<<endl;
  }


}

Subtask #1
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 1656 KB Output isn't correct
2 Incorrect 74 ms 1656 KB Output isn't correct
3 Incorrect 74 ms 1784 KB Output isn't correct
4 Incorrect 74 ms 1656 KB Output isn't correct
5 Incorrect 74 ms 1784 KB Output isn't correct
6 Incorrect 75 ms 1816 KB Output isn't correct
7 Incorrect 74 ms 1784 KB Output isn't correct
8 Incorrect 74 ms 1784 KB Output isn't correct
9 Correct 324 ms 2084 KB Output is correct
10 Correct 330 ms 2024 KB Output is correct
11 Correct 65 ms 1648 KB Output is correct
12 Correct 125 ms 3248 KB Output is correct
13 Correct 187 ms 4648 KB Output is correct
14 Correct 300 ms 6136 KB Output is correct
15 Incorrect 308 ms 7820 KB Output isn't correct
16 Correct 437 ms 9188 KB Output is correct
17 Correct 515 ms 10620 KB Output is correct
18 Correct 520 ms 12152 KB Output is correct
19 Correct 831 ms 13860 KB Output is correct
20 Correct 508 ms 10628 KB Output is correct