oj.uz

Submission #1108987

# Submission time Handle Problem Language Result Execution time Memory
1108987 2024-11-05T18:28:15 Z yazansh Job Scheduling (CEOI12_jobs) C++17
80 / 100
 393 ms 45412 KB 
/*************
  the author:     
  shimutski_zoro   
************ */
#include <bits/stdc++.h>
using namespace std;
#define yon(x) cout<<((x)?"YES":"NO");
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ff first 
#define ss second
#define em emplace_back
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define per(i,j,k) for(int i=k;i>=j;i--)
#define forp(x,y,a) for(auto &[x,y]:(a))
typedef long long  ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<pll> vpl;
typedef vector<vl> vvl;
typedef vector<vpl> vvpl;
typedef vector<string> vs;
typedef deque<ll> dl;
const int mod=1e9+7;
ll inf =1e18+1;
const int M=1e6;
const int N=1e3+1; 
const ll dx[]={1,0,-1,0},dy[]={0,1,0,-1};
void solve(){
ll n,m,d;
cin>>n>>d>>m;
vl a(m);
rep(i,0,m-1)cin>>a[i];
vl idx(m);
iota(all(idx),0LL);
sort(all(idx),[&](ll i ,ll j){return a[i]<a[j];});
sort(all(a));

 function<pair<bool,vvl>(ll)>check=[&](ll r)->pair<bool,vvl>{
  vvl tmp=vvl (n+1);
ll cnt=0;
rep(i,1,n){
  rep(j,1,r){
    if(cnt==m)return {1,tmp};
    if(a[cnt]>i)
    break;
if(a[cnt]+d>=i){
//cout<<cnt<<" "<<a[cnt]<<" "<<idx[cnt]<<" "<<i<<endl;
  tmp[i-1].em(idx[cnt++]+1);
}else return {0,tmp};
if(cnt==m)return {1,tmp};
  }
 
}
return {0,tmp};
 
 };
 // 1 1 2 2 2 3 3 4 4 5 6 6
 //0 4 1 3 8 
 vvl v;
 ll lo=1,hi=m;
 ll ans=m;
 while(lo<=hi){
  ll mid= lo + (hi-lo)/2;
  auto[ x,tmp]=check(mid);
if(x){
  hi=mid-1;
  ans=mid;
  v=tmp;
}else{
  lo=mid+1;
}
 }
cout<<ans<<endl;
//vvl v(n+1);
rep(i,0,n-1){
  if(v[i].size())
  for(auto it:v[i]){
    cout<<it<<" ";
  }
  cout<<0<<"\n";
}
}
 
 
signed main()
{
 
    ios_base::sync_with_stdio(NULL);
    cin.tie(nullptr);
    cout.tie(nullptr);
    #ifdef Usaco
    string f="herding";
    freopen((f+".in").c_str(),"r",stdin);
    freopen((f+".out").c_str(),"w",stdout);
    #endif
   int t = 1;
//cin >> t;
    while (t--)
    {
      solve();
    //  if(t>0)
      //cout<<endl;
    }
}
/*
*/

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5392 KB Output is correct
2 Correct 39 ms 5380 KB Output is correct
3 Correct 37 ms 5392 KB Output is correct
4 Correct 40 ms 5408 KB Output is correct
5 Correct 41 ms 5392 KB Output is correct
6 Correct 42 ms 5392 KB Output is correct
7 Correct 38 ms 5404 KB Output is correct
8 Correct 37 ms 5408 KB Output is correct
9 Correct 82 ms 12048 KB Output is correct
10 Correct 82 ms 12092 KB Output is correct
11 Correct 35 ms 4856 KB Output is correct
12 Correct 93 ms 9072 KB Output is correct
13 Correct 117 ms 14456 KB Output is correct
14 Correct 187 ms 20028 KB Output is correct
15 Correct 210 ms 21708 KB Output is correct
16 Correct 244 ms 26756 KB Output is correct
17 Runtime error 310 ms 34956 KB Memory limit exceeded
18 Runtime error 373 ms 35828 KB Memory limit exceeded
19 Runtime error 393 ms 45412 KB Memory limit exceeded
20 Runtime error 320 ms 34832 KB Memory limit exceeded