oj.uz

Submission #1108986

# Submission time Handle Problem Language Result Execution time Memory
1108986 2024-11-05T18:25:21 Z yazansh Job Scheduling (CEOI12_jobs) C++17
80 / 100
 484 ms 45820 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(n+1);
 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){
  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 41 ms 5396 KB Output is correct
2 Correct 40 ms 5392 KB Output is correct
3 Correct 40 ms 5388 KB Output is correct
4 Correct 39 ms 5396 KB Output is correct
5 Correct 48 ms 5364 KB Output is correct
6 Correct 43 ms 5388 KB Output is correct
7 Correct 40 ms 5532 KB Output is correct
8 Correct 41 ms 5388 KB Output is correct
9 Correct 90 ms 11564 KB Output is correct
10 Correct 51 ms 12880 KB Output is correct
11 Correct 36 ms 4912 KB Output is correct
12 Correct 94 ms 9056 KB Output is correct
13 Correct 121 ms 14488 KB Output is correct
14 Correct 176 ms 19968 KB Output is correct
15 Correct 213 ms 21640 KB Output is correct
16 Correct 249 ms 26728 KB Output is correct
17 Runtime error 317 ms 34876 KB Memory limit exceeded
18 Runtime error 383 ms 35820 KB Memory limit exceeded
19 Runtime error 484 ms 45820 KB Memory limit exceeded
20 Runtime error 329 ms 34948 KB Memory limit exceeded