oj.uz

Submission #1108990

# Submission time Handle Problem Language Result Execution time Memory
1108990 2024-11-05T18:31:42 Z yazansh Job Scheduling (CEOI12_jobs) C++17
80 / 100
 405 ms 45592 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<<lo<<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;
    }
}
/*
*/

Compilation message

jobs.cpp: In function 'void solve()':
jobs.cpp:62:5: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   62 |  ll ans=m;
      |     ^~~

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5392 KB Output is correct
2 Correct 41 ms 5384 KB Output is correct
3 Correct 40 ms 5392 KB Output is correct
4 Correct 39 ms 5384 KB Output is correct
5 Correct 41 ms 5408 KB Output is correct
6 Correct 39 ms 5360 KB Output is correct
7 Correct 38 ms 5392 KB Output is correct
8 Correct 43 ms 5404 KB Output is correct
9 Correct 80 ms 12012 KB Output is correct
10 Correct 81 ms 12096 KB Output is correct
11 Correct 35 ms 5024 KB Output is correct
12 Correct 93 ms 9132 KB Output is correct
13 Correct 120 ms 14444 KB Output is correct
14 Correct 183 ms 20112 KB Output is correct
15 Correct 240 ms 21616 KB Output is correct
16 Correct 284 ms 26812 KB Output is correct
17 Runtime error 322 ms 34936 KB Memory limit exceeded
18 Runtime error 405 ms 35820 KB Memory limit exceeded
19 Runtime error 399 ms 45592 KB Memory limit exceeded
20 Runtime error 338 ms 34900 KB Memory limit exceeded