Submission #455174

#	Time	Username	Problem	Language	Result	Execution time	Memory
455174		inluminas	Job Scheduling (CEOI12_jobs)	C++14	45 / 100	231 ms	38508 KiB

jobs

#include"bits/stdc++.h"
using namespace std;

#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)

const int lmt=1e6+1;
vector<int>adj[lmt];
int n,d,m,cnt[lmt];

bool ok(int sz){
  memset(cnt,0,sizeof cnt);
  for(int i=n;i>0;i--){
    cnt[i]=adj[i].size();
  }
  int r=n;
  for(int i=n;i>0;i--){
    for(r=min(r,i+d);r>i;r--){
      int left=sz-cnt[r];
      left=min(left,cnt[i]);
      cnt[i]-=left;
      cnt[r]+=left;
      continue;
    }
    if(cnt[i]>sz) return false;
  }
  return true;
}

int main(){
  fastio;

  cin>>n>>d>>m;
  for(int i=1;i<=m;i++){
    int a;
    cin>>a;
    adj[a].push_back(i);
  }

  int lo=1,hi=1e9;
  while(hi-lo>1){
    int mid=(lo+hi)>>1;
    if(ok(mid)) hi=mid;
    else lo=mid;
  }
  int pos;
  if(ok(lo)) pos=lo;
  else pos=hi;

  cout<<pos<<endl;
  int r=n;
  for(int i=n;i>0;i--){
    for(r=min(r,i+d);r>i;r--){
      while(adj[r].size()<pos && !adj[i].empty()){
        adj[r].push_back(adj[i].back());
        adj[i].pop_back();
      }
      if(adj[i].empty()) break;
    }
  }

  for(int i=1;i<=n;i++){
    for(int v:adj[i]) cout<<v<<" ";
    cout<<0<<endl;
  }

  return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:55:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |       while(adj[r].size()<pos && !adj[i].empty()){
      |             ~~~~~~~~~~~~~^~~~

• Subtask 1: 45 / 100