oj.uz

Submission #1108997

# Submission time Handle Problem Language Result Execution time Memory
1108997 2024-11-05T18:37:33 Z yazansh Job Scheduling (CEOI12_jobs) C++17
80 / 100
 279 ms 44908 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;
vpl a(m);
rep(i,0,m-1)cin>>a[i].ff , a[i].ss=i;
sort(all(a));
//forp(x,y,a)cout<<x<<" "<<y<<"\n";
vvl tmp(n);
 function<bool(ll)>check=[&](ll r)->bool{
  tmp=vvl (n);
ll cnt=0;
rep(i,1,n){
  rep(j,1,r){
    if(a[cnt].ff>i)
    break;
if(a[cnt].ff+d<i){
return 0;
}else{
  tmp[i-1].em(a[cnt].ss);
  cnt++;
}
if(cnt>=m)return 1;
  }

}
return 0;

 };
 vvl v;
 ll lo=1,hi=m;
 while(lo<=hi){
  ll mid= lo + (hi-lo)/2;
if(check(mid)){
  hi=mid-1;
  v=tmp;
}else{
  lo=mid+1;
}
 }
cout<<lo<<endl;
//vvl v(n+1);
rep(i,0,n-1){
  for(auto it:v[i]){
    cout<<it+1<<" ";
  }
  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 32 ms 5124 KB Output is correct
2 Correct 32 ms 5132 KB Output is correct
3 Correct 33 ms 5144 KB Output is correct
4 Correct 34 ms 5132 KB Output is correct
5 Correct 31 ms 5132 KB Output is correct
6 Correct 32 ms 5124 KB Output is correct
7 Correct 30 ms 5164 KB Output is correct
8 Correct 34 ms 5132 KB Output is correct
9 Correct 49 ms 13416 KB Output is correct
10 Correct 42 ms 14116 KB Output is correct
11 Correct 33 ms 4680 KB Output is correct
12 Correct 55 ms 8860 KB Output is correct
13 Correct 80 ms 14112 KB Output is correct
14 Correct 129 ms 19244 KB Output is correct
15 Correct 129 ms 21332 KB Output is correct
16 Correct 198 ms 26112 KB Output is correct
17 Runtime error 220 ms 33756 KB Memory limit exceeded
18 Runtime error 219 ms 34928 KB Memory limit exceeded
19 Runtime error 279 ms 44908 KB Memory limit exceeded
20 Runtime error 218 ms 33760 KB Memory limit exceeded