Submission #636945

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
636945	2022-08-30T15:42:27 Z	Omar_Elgedawy	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	362 ms	18764 KB

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[1000001],freq2[1000001];
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

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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	2112 KB	Output is correct
2	Correct	35 ms	2056 KB	Output is correct
3	Correct	36 ms	2128 KB	Output is correct
4	Correct	39 ms	2112 KB	Output is correct
5	Correct	35 ms	2028 KB	Output is correct
6	Correct	36 ms	2132 KB	Output is correct
7	Correct	36 ms	2096 KB	Output is correct
8	Correct	37 ms	2152 KB	Output is correct
9	Correct	149 ms	5528 KB	Output is correct
10	Correct	139 ms	5324 KB	Output is correct
11	Correct	33 ms	1980 KB	Output is correct
12	Correct	55 ms	3580 KB	Output is correct
13	Correct	82 ms	6720 KB	Output is correct
14	Correct	138 ms	8480 KB	Output is correct
15	Correct	134 ms	9676 KB	Output is correct
16	Correct	199 ms	12504 KB	Output is correct
17	Correct	241 ms	15564 KB	Output is correct
18	Correct	231 ms	14924 KB	Output is correct
19	Correct	362 ms	18764 KB	Output is correct
20	Correct	245 ms	15504 KB	Output is correct