Submission #636944

#	Time	Username	Problem	Language	Result	Execution time	Memory
636944		Omar_Elgedawy	Job Scheduling (CEOI12_jobs)	C++14	85 / 100	251 ms	23252 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define F first
#define S second
#define el endl
#define cout(x) for(auto v:x)cout<<v<<' '
#define cin(x) for(auto &v:x)cin>>v;
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()
int freq1[10001],freq2[10001];
void testcases(int h){
  int n,m,d;cin>>n>>d>>m;
  vector<int>v[n+d+1];
  for(int i=0;i<m;i++){
    int x;cin>>x;
    freq1[x]++;
    freq2[x]++;
    v[x].push_back(i+1);
  }
  int l=1,r=3e5,ans;
  while(l<=r){
    int mid=(l+r)/2;
    int num=1,f=1;
    for(int i=1;i<=n;i++){
      int cur=mid;
      if(i>num+d){
        f=0;
        break;
      }
      while(cur && freq1[num]<=cur && num<=i){
        cur-=freq1[num];
        freq1[num]=0;
        num++;
      }
      if(cur && num<=i){
        freq1[num]=freq1[num]-cur;
        cur=0;
      }
    }
    if(f){
      ans=mid;
      r=mid-1;
    }
    else{
      l=mid+1;
    }
    for(int i=1;i<=n;i++){
      freq1[i]=freq2[i];
    }
  }
  cout<<ans<<el;
  int num=1;
  for(int i=1;i<=n;i++){
    int cur=ans;
    // cout<<i<<" = ";
    while(cur && freq1[num]<=cur && num<=i){
      // cout<<"("<<num<<") : ";
      while(v[num].size()){
        cout<<v[num].back()<<' ';
        v[num].pop_back();
      }
      cur-=freq1[num];
      freq1[num]=0;
      num++;
    }
    if(cur && num<=i){
      freq1[num]=freq1[num]-cur;
      // cout<<"("<<num<<") : ";
      while(cur--){
        cout<<v[num].back()<<' ';
        v[num].pop_back();
      }
    }
    cout<<0<<el;
  }
}
int32_t main()
{
  int tc=1;
  // cin>>tc;
  for(int i=1;i<=tc;i++)testcases(i);
  return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'void testcases(long long int)':
jobs.cpp:63:10: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |       cur-=freq1[num];
      |       ~~~^~~~~~~~~~~~

• Subtask 1: 85 / 100